Problem: Saving electricity is very important!

You are in the office represented as R \times C grid that consists of walls and rooms. It is guaranteed that, for any pair of rooms in the office, there exists exactly one route between the two rooms. It takes 1 unit of time for you to move to the next room (that is, the grid adjacent to the current room). Rooms are so dark that you need to switch on a light when you enter a room. When you leave the room, you can either leave the light on, or of course you can switch off the light. Each room keeps consuming electric power while the light is on.

Today you have a lot of tasks across the office. Tasks are given as a list of coordinates, and they need to be done in the specified order. To save electricity, you want to finish all the tasks with the minimal amount of electric power.

The problem is not so easy though, because you will consume electricity not only when light is on, but also when you switch on/off the light. Luckily, you know the cost of power consumption per unit time and also the cost to switch on/off the light for all the rooms in the office. Besides, you are so smart that you don't need any time to do the tasks themselves. So please figure out the optimal strategy to minimize the amount of electric power consumed.

After you finished all the tasks, please DO NOT leave the light on at any room. It's obviously wasting!



Input

The first line of the input contains three positive integers R (0 \lt R \leq 50), C (0 \lt C \leq 50) and M (2 \leq M \leq 1000). The following R lines, which contain C characters each, describe the layout of the office. '.' describes a room and '#' describes a wall.

This is followed by three matrices with R rows, C columns each. Every elements of the matrices are positive integers. The (r, c) element in the first matrix describes the power consumption per unit of time for the room at the coordinate (r, c). The (r, c) element in the second matrix and the third matrix describe the cost to turn on the light and the cost to turn off the light, respectively, in the room at the coordinate (r, c).

Each of the last M lines contains two positive integers, which describe the coodinates of the room for you to do the task.

Note that you cannot do the i-th task if any of the j-th task (0 \leq j \leq i) is left undone.

Output

Print one integer that describes the minimal amount of electric power consumed when you finished all the tasks.

Examples

Input

1 3 2
...
1 1 1
1 2 1
1 1 1
0 0
0 2


Output

7


Input

3 3 5
...
.##
..#
1 1 1
1 0 0
1 1 0
3 3 3
3 0 0
3 3 0
5 4 5
4 0 0
5 4 0
1 0
2 1
0 2
2 0
0 0


Output

77


Input

5 5 10
.###
....
.#
..#.#
....
0 12 0 0 0
0 4 3 2 10
0 0 0 99 0
11 13 0 2 0
0 1 1 2 1
0 4 0 0 0
0 13 8 2 4
0 0 0 16 0
1 1 0 2 0
0 2 3 1 99
0 2 0 0 0
0 12 2 12 2
0 0 0 3 0
4 14 0 16 0
0 2 14 2 90
0 1
3 0
4 4
1 4
1 1
4 4
1 1
4 3
3 0
1 4


Output

777

Solution (in JAVA):

Solution:

import java.awt.Point;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	InputStream is;

	boolean __FILE_DEBUG_FLAG__ = false;
	String __DEBUG_FILE_NAME__ = "src/2156-input.txt";

	FastScanner in;
	PrintWriter out;
	
	class State implements Comparable<State> {
		int x;
		int y;
		int t;

		State(int x, int y, int t) {
			this.x = x;
			this.y = y;
			this.t = t;
		}

		public int compareTo(State s) {
			return dist[y][x] - dist[s.y][s.x];
		}

		public String toString() {
			return getClass().getName() + " : " + x + " " + y + " " + t;
		}
	}
	
	int NOT_YET = -1;
	int INF = 100000000;
	int[] vx = {-1, 0, 1, 0};
	int[] vy = {0, -1, 0, 1};
	
	int passedTime = 0;
	long res = 0;
	
	int[][] dist, prev;
	int[][] prevVisitTime;
	int[][] unitCost, onCost, offCost;
	char[][] room;
	
	boolean inside(int x, int y, int M, int N) {
		return x >= 0 && y >= 0 && x < M && y < N;
	}
	
	void bfs(int sx, int sy) {
		int R = dist.length, C = dist[0].length;
		for (int i = 0; i < R; i++) {
			Arrays.fill(dist[i], INF);
			Arrays.fill(prev[i], -1);
		}
		
		dist[sy][sx] = 0;
		
		Queue<State> q = new LinkedList<State>();
		q.add(new State(sx, sy, passedTime));
		while (!q.isEmpty()) {
			State st = q.poll();
			
			for (int d = 0; d < vx.length; d++) {
				int nx = st.x + vx[d], ny = st.y + vy[d];
				if (inside(nx, ny, C, R) && room[ny][nx] == '.') {
					int ncost = dist[st.y][st.x] + onCost[ny][nx] + offCost[ny][nx];
					if (prevVisitTime[ny][nx] != -1) 
						ncost = Math.min(ncost, dist[st.y][st.x] + unitCost[ny][nx] * (st.t + 1 - prevVisitTime[ny][nx]));
					
					if (ncost < dist[ny][nx]) {
						dist[ny][nx] = ncost;
						prev[ny][nx] = (d + 2) % 4;
						q.add(new State(nx, ny, st.t + 1));
					}
				}
			}
		}
		
//		mapDebug(dist);
//		mapDebug(prev);
	}
	
	void updateTime(int x, int y, int gx, int gy) {
//		System.out.println("upd : " + x + " " + y + " " + gx + " " + gy);
		if (x == gx && y == gy) return;
		
		int d = prev[y][x];
		updateTime(x + vx[d], y + vy[d], gx, gy);
		
		passedTime++;
		prevVisitTime[y][x] = passedTime;
	}
	
	public void solve() {	
		int R = in.nextInt(), C = in.nextInt(), M = in.nextInt();
		room = new char[R][];
		for (int i = 0; i < R; i++) {
			room[i] = in.next().toCharArray();
		}
		unitCost = in.nextIntMap(R, C);
		onCost = in.nextIntMap(R, C);
		offCost = in.nextIntMap(R, C);
		
		prevVisitTime = new int[R][C];
		for (int i = 0; i < R; i++) {
			Arrays.fill(prevVisitTime[i], NOT_YET);
		}
		dist = new int[R][C];
		prev = new int[R][C];
		
		int y = in.nextInt(), x = in.nextInt();
		res += onCost[y][x] + offCost[y][x];
		prevVisitTime[y][x] = 0;
		
		for (int i = 1; i < M; i++) {
			int ny = in.nextInt(), nx = in.nextInt();
			
			bfs(x, y);
			updateTime(nx, ny, x, y);
			res += dist[ny][nx];
			
			x = nx;
			y = ny;
		}
		
		System.out.println(res);
	}

	
	public void run() {
		if (__FILE_DEBUG_FLAG__) {
			try {
				is = new FileInputStream(__DEBUG_FILE_NAME__);
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
			System.out.println("FILE_INPUT!!");
		} else {
			is = System.in;
		}
		in = new FastScanner(is);
		out = new PrintWriter(System.out);

		solve();
	}

	public static void main(String[] args) {
		new Main().run();
	}

	public void mapDebug(int[][] a) {
		System.out.println("--------map display---------");

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.printf("%3d ", a[i][j]);
			}
			System.out.println();
		}

		System.out.println("----------------------------");
		System.out.println();
	}

	public void debug(Object... obj) {
		System.out.println(Arrays.deepToString(obj));
	}

	class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
			//stream = new FileInputStream(new File("dec.in"));

		}

		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++];
		}

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

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

		int nextInt() {
			return Integer.parseInt(next());
		}

		int[] nextIntArray(int n) {
			int[] array = new int[n];
			for (int i = 0; i < n; i++)
				array[i] = nextInt();

			return array;
		}

		int[][] nextIntMap(int n, int m) {
			int[][] map = new int[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextIntArray(m);
			}
			return map;
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		long[] nextLongArray(int n) {
			long[] array = new long[n];
			for (int i = 0; i < n; i++)
				array[i] = nextLong();

			return array;
		}

		long[][] nextLongMap(int n, int m) {
			long[][] map = new long[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextLongArray(m);
			}
			return map;
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		double[] nextDoubleArray(int n) {
			double[] array = new double[n];
			for (int i = 0; i < n; i++)
				array[i] = nextDouble();

			return array;
		}

		double[][] nextDoubleMap(int n, int m) {
			double[][] map = new double[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextDoubleArray(m);
			}
			return map;
		}

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

		String[] nextStringArray(int n) {
			String[] array = new String[n];
			for (int i = 0; i < n; i++)
				array[i] = next();

			return array;
		}

		String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}
}