[코드트리] 나무박멸

import sys
input = sys.stdin.readline

ddx = (-1, -1, 1, 1)
ddy = (-1, 1, -1, 1)
dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)

N, M, K, C = map(int, input().split())
board = [list(map(int, input().split())) for n in range(N)]

def upgrade_tree():
    adj_tree = dict()
    for x in range(N):
        for y in range(N):
            if board[x][y] > 0:
                adj_tree[(x, y)] = [0, 0] #[인접한 빈 칸 개수, 인접한 나무가 있는 칸 개수]
                for d in range(4):
                    nx=x+dx[d]; ny=y+dy[d]
                    if 0<=nx<N and 0<=ny<N:
                        if board[nx][ny] == 0 and herbicide[nx][ny] == 0:
                            adj_tree[(x, y)][0] += 1
                            adj_tree[(x, y)].append(d)
                        if board[nx][ny] > 0 and herbicide[nx][ny] == 0:
                            adj_tree[(x, y)][1] += 1

    for tree_pos in adj_tree.keys():
        x, y = tree_pos
        board[x][y] += adj_tree[tree_pos][1]
        if adj_tree[tree_pos][0] != 0: n = board[x][y] // adj_tree[tree_pos][0]
        else: n = 0
        for d in adj_tree[tree_pos][2:]:
            nx=x+dx[d]; ny=y+dy[d]
            board[nx][ny] += n

def disperse_herbicide():
    global total_tree_cnt

    ### 가장 많은 나무 박멸시키는 칸 찾기
    kx, ky = -1, -1; tree_cnt_li = []
    for x in range(N):
        for y in range(N):
            if board[x][y] > 0:
                tree_cnt = board[x][y]
                for i in range(4):
                    nx=x; ny=y
                    for k in range(K):
                        nx+=ddx[i]; ny+=ddy[i]
                        if 0<=nx<N and 0<=ny<N:
                            if board[nx][ny] == -1 or board[nx][ny] == 0: break
                            elif board[nx][ny] > 0: tree_cnt += board[nx][ny]
                tree_cnt_li.append((-tree_cnt, x, y))
    if tree_cnt_li:
        tree_cnt_li.sort(); kx, ky = tree_cnt_li[0][1], tree_cnt_li[0][2]
        total_tree_cnt += -tree_cnt_li[0][0]

    ### herbicide 카운트 -1
    for x in range(N):
        for y in range(N):
            if herbicide[x][y] > 0: herbicide[x][y] -= 1

    ### 해당 칸에 제초제 뿌리기
    board[kx][ky] = 0; herbicide[kx][ky] = C
    for i in range(4):
        nx=kx; ny=ky
        for k in range(K):
            nx+=ddx[i]; ny+=ddy[i]
            if 0<=nx<N and 0<=ny<N:
                if board[nx][ny] == -1: break
                elif board[nx][ny] == 0: herbicide[nx][ny] = C; break
                elif board[nx][ny] > 0: board[nx][ny] = 0; herbicide[nx][ny] = C


herbicide = [[0]*N for n in range(N)]
total_tree_cnt = 0
for m in range(M):
    upgrade_tree()
    disperse_herbicide()
print(total_tree_cnt)