Problem: They've screwed something up yet again... In one nuclear reactor of a research station an uncontrolled reaction is in progress and explosion which will destroy the whole station will happen soon.

The station is represented by a square n × n divided into 1 × 1 blocks. Each block is either a reactor or a laboratory. There can be several reactors and exactly one of them will explode soon. The reactors can be considered impassable blocks, but one can move through laboratories. Between any two laboratories, which are in adjacent blocks, there is a corridor. Blocks are considered adjacent if they have a common edge.

In each laboratory there is some number of scientists and some number of rescue capsules. Once the scientist climbs into a capsule, he is considered to be saved. Each capsule has room for not more than one scientist.

The reactor, which is about to explode, is damaged and a toxic coolant trickles from it into the neighboring blocks. The block, which contains the reactor, is considered infected. Every minute the coolant spreads over the laboratories through corridors. If at some moment one of the blocks is infected, then the next minute all the neighboring laboratories also become infected. Once a lab is infected, all the scientists there that are not in rescue capsules die. The coolant does not spread through reactor blocks.

There are exactly t minutes to the explosion. Any scientist in a minute can move down the corridor to the next lab, if it is not infected. On any corridor an unlimited number of scientists can simultaneously move in both directions. It is believed that the scientists inside a lab moves without consuming time. Moreover, any scientist could get into the rescue capsule instantly. It is also believed that any scientist at any given moment always has the time to perform their actions (move from the given laboratory into the next one, or climb into the rescue capsule) before the laboratory will be infected.

Find the maximum number of scientists who will be able to escape.

Input

The first line contains two integers n and t (2 ≤ n ≤ 10, 1 ≤ t ≤ 60). Each of the next n lines contains n characters. These lines describe the scientists' locations. Then exactly one empty line follows. Each of the next n more lines contains n characters. These lines describe the rescue capsules' locations.

In the description of the scientists' and the rescue capsules' locations the character "Y" stands for a properly functioning reactor, "Z" stands for the malfunctioning reactor. The reactors' positions in both descriptions coincide. There is exactly one malfunctioning reactor on the station. The digits "0" - "9" stand for the laboratories. In the description of the scientists' locations those numbers stand for the number of scientists in the corresponding laboratories. In the rescue capsules' descriptions they stand for the number of such capsules in each laboratory.

Output

Print a single number — the maximum number of scientists who will manage to save themselves.

Examples

Input

3 3
1YZ
1YY
100

0YZ
0YY
003


Output

2

Input

4 4
Y110
1Y1Z
1Y0Y
0100

Y001
0Y0Z
0Y0Y
0005


Output

3

Note

In the second sample the events could take place as follows: 

<image>

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Collection;
import java.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author AlexFetisov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    private static final int INF = (int) 1e9;
    int n;
    int timeExplode;
    boolean[][] hasWall;
    int badStartX, badStartY;
    int[][] numberOfScientists;
    int[][] numberOfReactors;
    int[][] becomeBad;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        n = in.nextInt();
        timeExplode = in.nextInt();
        hasWall = new boolean[n][n];
        numberOfScientists = new int[n][n];
        numberOfReactors = new int[n][n];
        for (int i = 0; i < n; ++i) {
            String line = in.nextString();
            for (int j = 0; j < n; ++j) {
                char c = line.charAt(j);
                if (c == 'Z') {
                    badStartX = i;
                    badStartY = j;
                    hasWall[i][j] = true;
                } else if (c == 'Y') {
                    hasWall[i][j] = true;
                } else {
                    numberOfScientists[i][j] = c - '0';
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            String line = in.nextString();
            for (int j = 0; j < n; ++j) {
                char c = line.charAt(j);
                if (Character.isDigit(c)) {
                    numberOfReactors[i][j] = c - '0';
                }
            }
        }

        becomeBad = new int[n][n];
        ArrayUtils.fill(becomeBad, INF);
        becomeBad[badStartX][badStartY] = 0;
        int[] qx = new int[n * n];
        int[] qy = new int[n * n];
        int qSize = 1;
        qx[0] = badStartX;
        qy[0] = badStartY;
        for (int qi = 0; qi < qSize; ++qi) {
            int cx = qx[qi];
            int cy = qy[qi];
            for (int d = 0; d < dx.length; ++d) {
                int nx = cx + dx[d];
                int ny = cy + dy[d];
                if (isValid(nx, ny, n)) {
                    if (!hasWall[nx][ny]) {
                        if (becomeBad[nx][ny] == INF) {
                            becomeBad[nx][ny] = becomeBad[cx][cy] + 1;
                            qx[qSize] = nx;
                            qy[qSize] = ny;
                            ++qSize;
                        }
                    }
                }
            }
        }

        Graph maxFlowGraph = new Graph();
        maxFlowGraph.initGraphWithFlow(n * n * 2 + 2, n * n * n * n * 4 * 3 + 10 * n * n + 100);

        int source = 0;
        int shiftForPerson = 1;
        int shiftForReactor = n * n + 1;
        int dest = n * n + n * n + 1;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (numberOfScientists[i][j] > 0) {
                    maxFlowGraph.addFlowEdge(source, i * n + j + shiftForPerson, numberOfScientists[i][j]);
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (numberOfReactors[i][j] > 0) {
                    maxFlowGraph.addFlowEdge(i * n + j + shiftForReactor, dest, numberOfReactors[i][j]);
                }
            }
        }

        for (int xPerson = 0; xPerson < n; ++xPerson) {
            for (int yPerson = 0; yPerson < n; ++yPerson) {
                if (numberOfScientists[xPerson][yPerson] > 0) {
                    boolean[][] canReach = new boolean[n][n];
                    boolean[][] marked = new boolean[n][n];
                    boolean[][] newMarked = new boolean[n][n];
                    marked[xPerson][yPerson] = true;
                    canReach[xPerson][yPerson] = true;
                    for (int curTime = 0; curTime < timeExplode; ++curTime) {
                        for (int i = 0; i < n; ++i) {
                            for (int j = 0; j < n; ++j) {
                                if (marked[i][j]) {
                                    for (int d = 0; d < 4; ++d) {
                                        int ni = i + dx[d];
                                        int nj = j + dy[d];
                                        if (isValid(ni, nj, n)) {
                                            if (!hasWall[ni][nj]) {
                                                if (curTime + 1 <= becomeBad[ni][nj]) {
                                                    canReach[ni][nj] = true;
                                                }
                                                if (curTime + 1 < becomeBad[ni][nj]) {
                                                    newMarked[ni][nj] = true;
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                        for (int i = 0; i < n; ++i) {
                            for (int j = 0; j < n; ++j) {
                                marked[i][j] = newMarked[i][j];
                                newMarked[i][j] = false;
                            }
                        }
                    }
                    for (int xReactor = 0; xReactor < n; ++xReactor) {
                        for (int yReactor = 0; yReactor < n; ++yReactor) {
                            if (numberOfReactors[xReactor][yReactor] > 0) {
                                if (canReach[xReactor][yReactor]) {
                                    maxFlowGraph.addFlowEdge(xPerson * n + yPerson + shiftForPerson, xReactor * n + yReactor + shiftForReactor, INF);
                                }
                            }
                        }
                    }
                }
            }
        }
        long flow = MaxFlowDinic.dinic(maxFlowGraph, source, dest);
        out.println(flow);
    }

    private boolean isValid(int x, int y, int n) {
        return x >= 0 && y >= 0 && x < n && y < n;
    }

    int[] dx = new int[] {1, 0, -1, 0};
    int[] dy = new int[] {0, 1, 0, -1};
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

}

class ArrayUtils {

    public static void fill(int[][] f, int value) {
        for (int i = 0; i < f.length; ++i) {
            Arrays.fill(f[i], value);
        }
    }

}

class Graph {
    public int[] from;
    public int[] to;
    public int[] first;
    public int[] next;
    public int[] cost;
    public int[] capacity;
    public long[] flow;
    public int[] last;
    public int nVertex;
    public int nEdges;
    int[] reverseEdge;
    public int curEdge;

    public Graph() {}

    public void initGraphWithFlow(int n, int m) {
        curEdge = 0;
        nVertex = n;
        nEdges = m;
        from = new int[m * 2];
        to = new int[m * 2];
        first = new int[n];
        next = new int[m * 2];
        cost = new int[m * 2];
        capacity = new int[m * 2];
        flow = new long[m * 2];
        reverseEdge = new int[m * 2];
        last = new int[m * 2];
        Arrays.fill(first, -1);
        Arrays.fill(last, -1);
    }

    public void addFlowEdge(int a, int b, int f) {
//        System.err.println("Added edge " + a + " - " + b + " with flow: " + f);
        next[curEdge] = first[a];
        first[a] = curEdge;
        to[curEdge] = b;
        from[curEdge] = a;
        capacity[curEdge] = f;
        flow[curEdge] = 0;
        reverseEdge[curEdge] = curEdge + 1;
        ++curEdge;

        next[curEdge] = first[b];
        first[b] = curEdge;
        to[curEdge] = a;
        from[curEdge] = b;
        capacity[curEdge] = 0;
        flow[curEdge] = 0;
        reverseEdge[curEdge] = curEdge - 1;
        ++curEdge;
    }

    public final void pushFlow(int id, long fl) {
        if (fl == 0) {
            return;
        }
        flow[id] += fl;
        flow[id^1] -= fl;
    }

}

class MaxFlowDinic {
    private final Graph graph;
    private int source;
    private int dest;
    private int[] queue;
    private int[] distance;
    private int[] nextEdge;

    public MaxFlowDinic(Graph graph, int source, int dest) {
        this.graph = graph;
        this.source = source;
        this.dest = dest;
        int n = graph.nVertex;
        queue = new int[n];
        distance = new int[n];
        nextEdge = new int[n];
    }

    public static long dinic(Graph graph, int source, int destination) {
        return new MaxFlowDinic(graph, source, destination).dinic();
    }

    private long dinic() {
        long totalFlow = 0;
        while (true) {
            edgeDistances();
            if (distance[dest] == -1)
                break;
            Arrays.fill(nextEdge, -2);
            totalFlow += dinicImpl(source, Long.MAX_VALUE);
        }
        return totalFlow;
    }

    private void edgeDistances() {
        Arrays.fill(distance, -1);
        distance[source] = 0;
        int size = 1;
        queue[0] = source;
        for (int i = 0; i < size; i++) {
            int cur = queue[i];
            for (int id = graph.first[cur]; id != -1; id = graph.next[id]) {
                if (graph.capacity[id] > graph.flow[id]) {
                    int next = graph.to[id];
                    if (distance[next] == -1) {
                        distance[next] = distance[cur] + 1;
                        queue[size++] = next;
                    }
                }
            }
        }
    }

    private long dinicImpl(int source, long flow) {
        if (source == dest) {
            return flow;
        }
        if (flow == 0 || distance[source] == distance[dest]) {
            return 0;
        }
        int id = nextEdge[source];
        if (id == -2) {
            nextEdge[source] = id = graph.first[source];
        }
        long totalPushed = 0;
        while (id != -1) {
            int nextDestinationID = graph.to[id];
            if (graph.capacity[id] > graph.flow[id] && distance[nextDestinationID] == distance[source] + 1) {
                long pushed = dinicImpl(nextDestinationID, Math.min(flow, graph.capacity[id] - graph.flow[id]));
                if (pushed != 0) {
                    graph.pushFlow(id, pushed);
                    flow -= pushed;
                    totalPushed += pushed;
                    if (flow == 0)
                        return totalPushed;
                }
            }
            nextEdge[source] = id = graph.next[id];
        }
        return totalPushed;
    }

}