[코드트리] 술래잡기

import sys
input = sys.stdin.readline

N, M, H, K = map(int, input().split())

person = dict() #[x, y, d, status]
person_match = dict() #(x, y) = person_num
for m in range(1, M+1):
    x, y, d = map(int, input().split())
    if d == 2: d = 0
    person[m] = [x-1, y-1, d, True]
    person_match[(x-1, y-1)] = set(); person_match[(x-1, y-1)].add(m)

board = [[0]*N for n in range(N)] #나무 표시 용
for h in range(H):
    x, y = map(int, input().split())
    board[x-1][y-1] = 1

def create_path():
    global path

    dx = (-1, 0, 1, 0) #상우하좌
    dy = (0, 1, 0, -1)

    d = 0; dist = 1; cnt = 0
    x = N//2; y = N//2; path[x][y] = d
    while True:
        for _ in range(dist):
            x += dx[d]; y += dy[d]
            path[x][y] = d
            if (x, y) == (0, 0): path[x][y] = 2; return
        d = (d+1)%4
        path[x][y] = d
        cnt += 1
        if cnt == 2:
            cnt = 0
            dist += 1

def create_htap():
    global htap

    dx = (-1, 0, 1, 0) #상우하좌
    dy = (0, 1, 0, -1)

    d = 2; dist = N-1; cnt = 0
    x = 0; y = 0; htap[x][y] = d
    htap[x][y] = d
    for _ in range(dist-1):
        x += dx[d]; y += dy[d]
        htap[x][y] = d
    x += dx[d]; y += dy[d]
    d -= 1; htap[x][y] = d
    while True:
        for _ in range(dist):
            x += dx[d]; y += dy[d]
            htap[x][y] = d
            if (x, y) == (N//2, N//2): htap[x][y] = 0; return
        d = (d-1)%4
        htap[x][y] = d
        cnt += 1
        if cnt == 2:
            cnt = 0
            dist -= 1

def move_person():
    global person, person_match, monster

    dx = (1, 0, -1, 0) #하우상좌
    dy = (0, 1, 0, -1)

    for m in person.keys():
        if person[m][3]:
            x, y, d, _ = person[m]
            if (abs(x-monster[0]) + abs(y-monster[1])) <= 3:
                nx, ny = x+dx[d], y+dy[d]
                if 0<=nx<N and 0<=ny<N:
                    if monster[0] != nx or monster[1] != ny:
                        person[m][0] = nx; person[m][1] = ny
                        person_match[(x, y)].remove(m)
                        if not person_match[(x, y)]: del person_match[(x, y)]
                        if (nx, ny) in person_match: person_match[(nx, ny)].add(m)
                        else: person_match[(nx, ny)] = set(); person_match[(nx, ny)].add(m)
                else:
                    d = (d+2)%4; person[m][2] = d
                    nx, ny = x+dx[d], y+dy[d]
                    if 0<=nx<N and 0<=ny<N:
                        if monster[0] != nx or monster[1] != ny:
                            person[m][0] = nx; person[m][1] = ny
                            person_match[(x, y)].remove(m)
                            if not person_match[(x, y)]: del person_match[(x, y)]
                            if (nx, ny) in person_match: person_match[(nx, ny)].add(m)
                            else: person_match[(nx, ny)] = set(); person_match[(nx, ny)].add(m)

def move_monster():
    global person, person_match, monster, path, htap, total_score, reverse_flag, k

    dx = (-1, 0, 1, 0) #상우하좌
    dy = (0, 1, 0, -1)

    x, y = monster[0], monster[1]
    if (x, y) == (0, 0): reverse_flag = True
    elif (x, y) == (N//2, N//2): reverse_flag = False

    d = -1
    if not reverse_flag: nx = x+dx[path[x][y]]; ny = y+dy[path[x][y]]; d = path[nx][ny]
    else: nx = x+dx[htap[x][y]]; ny = y+dy[htap[x][y]]; d = htap[nx][ny]
    monster[0] = nx; monster[1] = ny

    x, y = monster[0], monster[1]
    for _ in range(3):
        if 0<=x<N and 0<=y<N:
            if board[x][y] == 0:
                if (x, y) in person_match:
                    m = person_match[(x, y)]
                    total_score += len(m)*k
                    for ps in m: person[ps] = [-1, -1, -1, False]
                    del person_match[(x, y)]
        x += dx[d]; y += dy[d]

path = [[-1]*N for n in range(N)] ###술래의 경로
create_path()

htap = [[-1]*N for n in range(N)] ###술래의 역경로
create_htap()

total_score = 0
monster = [N//2, N//2]
reverse_flag = False
for k in range(1, K+1):
    move_person()
    move_monster()
print(total_score)