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.util.Collections;
import java.util.InputMismatchException;
import java.math.BigInteger;
import java.util.Stack;
import java.util.*;
import java.util.Set;
import java.util.Collection;
import java.util.ArrayList;
import java.util.List;
import java.util.Comparator;
import java.io.*;
import java.util.Iterator;
import java.util.HashSet;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.Arrays;

/**
 * Generated by Contest helper plug-in
 * Actual solution is at the bottom
 */
public class Main {
	public static void main(String[] args) {
		InputReader in = new StreamInputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		run(in, out);
	}

	public static void run(InputReader in, PrintWriter out) {
		Solver solver = new TaskE();
		solver.solve(1, in, out);
		Exit.exit(in, out);
	}
}

abstract class InputReader {
	private boolean finished = false;

	public abstract int read();

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public String readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuffer res = new StringBuffer();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	private boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public char readCharacter() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		return (char) c;
	}

	public void setFinished(boolean finished) {
		this.finished = finished;
	}

	public abstract void close();
}

class StreamInputReader extends InputReader {
	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar, numChars;

	public StreamInputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	@Override
	public void close() {
		try {
			stream.close();
		} catch (IOException ignored) {
		}
	}
}

class Exit {
	private Exit() {
	}

	public static void exit(InputReader in, PrintWriter out) {
		in.setFinished(true);
		in.close();
		out.close();
	}
}

interface Solver {
	public void solve(int testNumber, InputReader in, PrintWriter out);
}

class Pair<U, V> {

	public final U first;
	public final V second;

	public static<U, V> Pair<U, V> makePair(U first, V second) {
		return new Pair<U, V>(first, second);
	}

	private Pair(U first, V second) {
		this.first = first;
		this.second = second;
	}

	@Override
	public boolean equals(Object o) {
		if (this == o) return true;
		if (o == null || getClass() != o.getClass()) return false;

		Pair pair = (Pair) o;

		return !(first != null ? !first.equals(pair.first) : pair.first != null) && !(second != null ? !second.equals(pair.second) : pair.second != null);

	}

	@Override
	public int hashCode() {
		int result = first != null ? first.hashCode() : 0;
		result = 31 * result + (second != null ? second.hashCode() : 0);
		return result;
	}

	@Override
	public String toString() {
		return "(" + first + "," + second + ")";
	}
}

interface Edge {
	public int getSource();
	public int getDestination();
	public long getCapacity();
	public void pushFlow(long flow);
	public Edge getReverseEdge();
}

class Graph {
	private final int size;
	private final List<Edge>[] edges;

	public Graph(int size) {
		this.size = size;
		//noinspection unchecked
		edges = new List[size];
		for (int i = 0; i < size; i++)
			edges[i] = new ArrayList<Edge>();
	}

	public int getSize() {
		return size;
	}

	public List<Edge> getIncident(int vertex) {
		return edges[vertex];
	}

	public void add(Edge edge) {
		edges[edge.getSource()].add(edge);
		edge = edge.getReverseEdge();
		if (edge != null)
			edges[edge.getSource()].add(edge);
	}

	}

class GraphAlgorithms {
	public static long dinic(Graph graph, int source, int destination) {
		long totalFlow = 0;
		int vertexCount = graph.getSize();
		int[] nextEdge = new int[vertexCount];
		while (true) {
			long[] distance = edgeDistances(graph, source).getDistances();
			if (distance[destination] == Long.MAX_VALUE)
				break;
			Arrays.fill(nextEdge, 0);
			totalFlow += dinicImpl(graph, source, destination, Long.MAX_VALUE, distance, nextEdge);
		}
		return totalFlow;
	}

	private static DistanceResult edgeDistances(Graph graph, int source) {
		int size = graph.getSize();
		Deque<Integer> queue = new ArrayDeque<Integer>(size);
		boolean[] processed = new boolean[size];
		boolean[] notReached = new boolean[size];
		Arrays.fill(notReached, true);
		long[] distance = new long[size];
		int[] last = new int[size];
		Arrays.fill(distance, Long.MAX_VALUE);
		distance[source] = 0;
		last[source] = -1;
		queue.add(source);
		notReached[source] = false;
		int iterationCount = 0;
		while (!queue.isEmpty()) {
			iterationCount++;
			if (iterationCount / size / size / size != 0)
				return null;
			int current = queue.poll();
			processed[current] = true;
			for (Edge edge : graph.getIncident(current)) {
				if (edge.getCapacity() == 0)
					continue;
				int next = edge.getDestination();
				long weight = 1;
				if (distance[next] > distance[current] + weight) {
					distance[next] = distance[current] + weight;
					last[next] = current;
					if (notReached[next]) {
						notReached[next] = false;
						queue.add(next);
					} else if (processed[next]) {
						processed[next] = false;
						queue.addFirst(next);
					}
				}
			}
		}
		return new DistanceResult(distance, last);
	}

	private static long dinicImpl(Graph graph, int source, int destination, long flow, long[] distance, int[] nextEdge) {
		if (source == destination)
			return flow;
		if (flow == 0 || distance[source] == distance[destination])
			return 0;
		List<Edge> incident = graph.getIncident(source);
		int incidentSize = incident.size();
		int totalPushed = 0;
		for (int i = nextEdge[source]; i < incidentSize; i++) {
			Edge edge = incident.get(i);
			int nextDestination = edge.getDestination();
			if (distance[nextDestination] != distance[source] + 1)
				continue;
			long pushed = dinicImpl(graph, nextDestination, destination, Math.min(flow, edge.getCapacity()),
				distance, nextEdge);
			if (pushed != 0) {
				edge.pushFlow(pushed);
				flow -= pushed;
				totalPushed += pushed;
				if (flow == 0) {
					nextEdge[source] = i;
					return totalPushed;
				}
			}
		}
		nextEdge[source] = incidentSize;
		return totalPushed;
	}


	public static class DistanceResult {
		private final long[] distances;
		private final int[] last;

		public DistanceResult(long[] distances, int[] last) {
			this.distances = distances;
			this.last = last;
		}

		public long[] getDistances() {
			return distances;
		}

		}

	}

class SimpleEdge implements Edge {
	protected final int source;
	protected final int destination;

	public SimpleEdge(int source, int destination) {
		this.source = source;
		this.destination = destination;
	}

	public int getSource() {
		return source;
	}

	public int getDestination() {
		return destination;
	}

	public long getCapacity() {
		return 0;
	}

	public void pushFlow(long flow) {
		throw new UnsupportedOperationException();
	}

	public Edge getReverseEdge() {
		return null;
	}

	}

class FlowEdge extends SimpleEdge {
	private long capacity;
	private long flow = 0;
	private Edge reverseEdge;

	public FlowEdge(int source, int destination, long capacity) {
		super(source, destination);
		this.capacity = capacity;
		reverseEdge = new ReverseEdge();
	}

	@Override
	public long getCapacity() {
		return capacity;
	}

	@Override
	public void pushFlow(long flow) {
		if (flow > 0) {
			if (this.capacity < flow)
				throw new IllegalArgumentException();
		} else {
			if (this.flow < -flow)
				throw new IllegalArgumentException();
		}
		capacity -= flow;
		this.flow += flow;
	}

	@Override
	public Edge getReverseEdge() {
		return reverseEdge;
	}

	private class ReverseEdge implements Edge {
		public int getSource() {
			return destination;
		}

		public int getDestination() {
			return source;
		}

		public long getCapacity() {
			return flow;
		}

		public void pushFlow(long flow) {
			FlowEdge.this.pushFlow(-flow);
		}

		public Edge getReverseEdge() {
			return FlowEdge.this;
		}
	}
}

class IOUtils {

	public static char[] readCharArray(InputReader in, int size) {
		char[] array = new char[size];
		for (int i = 0; i < size; i++)
			array[i] = in.readCharacter();
		return array;
	}

	public static char[][] readTable(InputReader in, int rowCount, int columnCount) {
		char[][] table = new char[rowCount][];
		for (int i = 0; i < rowCount; i++)
			table[i] = readCharArray(in, columnCount);
		return table;
	}

	}

class MiscUtils {
	public static final int[] DX_4_CONNECTED = {1, 0, -1, 0};
	public static final int[] DY_4_CONNECTED = {0, -1, 0, 1};

	}

class TaskE implements Solver {
	public void solve(int testNumber, InputReader in, PrintWriter out) {
		int size = in.readInt();
		int time = in.readInt();
		char[][] scientists = IOUtils.readTable(in, size, size);
		char[][] rescue = IOUtils.readTable(in, size, size);
		Graph graph = new Graph(2 * size * size + 2);
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				if (Character.isDigit(scientists[i][j]))
					graph.add(new FlowEdge(2 * size * size, i * size + j, scientists[i][j] - '0'));
				if (Character.isDigit(rescue[i][j]))
					graph.add(new FlowEdge(size * size + i * size + j, 2 * size * size + 1, rescue[i][j] - '0'));
			}
		}
		int badRow = -1;
		int badColumn = -1;
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				if (rescue[i][j] == 'Z') {
					badRow = i;
					badColumn = j;
				}
			}
		}
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				if (Character.isDigit(scientists[i][j]) && scientists[i][j] != '0') {
					if (rescue[i][j] != '0')
						graph.add(new FlowEdge(i * size + j, size * size + i * size + j, Integer.MAX_VALUE));
					Set<Pair<Integer, Integer>> canBe = new HashSet<Pair<Integer, Integer>>();
					canBe.add(Pair.makePair(i, j));
					Set<Pair<Integer, Integer>> caNtBe = new HashSet<Pair<Integer, Integer>>();
					caNtBe.add(Pair.makePair(badRow, badColumn));
					for (int k = 0; k < time; k++) {
						Set<Pair<Integer, Integer>> nextCanBe = new HashSet<Pair<Integer, Integer>>();
						for (Pair<Integer, Integer> cell : canBe) {
							for (int l = 0; l < 4; l++) {
								int newRow = cell.first + MiscUtils.DX_4_CONNECTED[l];
								int newColumn = cell.second + MiscUtils.DY_4_CONNECTED[l];
								if (newRow >= 0 && newColumn >= 0 && newRow < size && newColumn < size && Character.isDigit(scientists[newRow][newColumn])) {
									Pair<Integer, Integer> next = Pair.makePair(newRow, newColumn);
									if (!caNtBe.contains(next)) {
										if (rescue[newRow][newColumn] != '0')
											graph.add(new FlowEdge(i * size + j, size * size + newRow * size + newColumn, Integer.MAX_VALUE));
										nextCanBe.add(next);
									}
								}
							}
						}
						Set<Pair<Integer, Integer>> nextCaNtBe = new HashSet<Pair<Integer, Integer>>();
						for (Pair<Integer, Integer> cell : caNtBe) {
							nextCaNtBe.add(cell);
							for (int l = 0; l < 4; l++) {
								int newRow = cell.first + MiscUtils.DX_4_CONNECTED[l];
								int newColumn = cell.second + MiscUtils.DY_4_CONNECTED[l];
								if (newRow >= 0 && newColumn >= 0 && newRow < size && newColumn < size && Character.isDigit(scientists[newRow][newColumn])) {
									Pair<Integer, Integer> next = Pair.makePair(newRow, newColumn);
									nextCaNtBe.add(next);
								}
							}
						}
						canBe = nextCanBe;
						caNtBe = nextCaNtBe;
						canBe.removeAll(caNtBe);
					}
				}
			}
		}
		out.println(GraphAlgorithms.dinic(graph, 2 * size * size, 2 * size * size + 1));
	}
}