Time Limit: 8 sec / Memory Limit: 64 MB





Example

Input

10 10
.....#....
.....#....
.....#....
######....
..........
####......
....###...
t..#..####
...##.....
....#...##
3
0 3
0 5
4 6


Output

2
#include<iostream>
#include<queue>
#include<tuple>
#include<algorithm>
using namespace std;
int X[2000][2000];
int V[2000][2000];
int H, W, K, SX, SY, X1, Y1; char c;
int main() {
	cin >> W >> H;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> c;
			if (c == '#') {
				X[i][j] = 2000;
			}
			if(c == '.') {
				X[i][j] = 0;
			}
			if (c == 't') {
				SX = i; SY = j;
				X[i][j] = 0;
			}
		}
	}
	cin >> K;
	for (int i = 1; i <= K; i++) {
		cin >> Y1 >> X1;
		X[X1][Y1] = i;
	}
	queue<tuple<int, int, int> >Q;
	for (int i = 0; i < 1000; i++) {
		for (int j = 0; j < 1000; j++) {
			V[i][j] = 3000;
		}
	}
	V[0][0] = 0;
	Q.push(make_tuple(0, 0, 0));
	while (!Q.empty()) {
		tuple<int, int, int>tup = Q.front();
		Q.pop();
		int a1 = get<0>(tup);
		int a2 = get<1>(tup);
		int a3 = get<2>(tup);
		
		if (a1 - 1 >= 0) {
			int a4 = X[a1 - 1][a2];
			a4 = max(a4, a3);
			if (V[a1 - 1][a2]>a4) {
				V[a1 - 1][a2] = a4;
				Q.push(make_tuple(a1 - 1, a2, V[a1 - 1][a2]));
			}
		}
		if (a1 + 1 < H) {
			int a4 = X[a1 + 1][a2];
			a4 = max(a4, a3);
			if (V[a1 + 1][a2]>a4) {
				V[a1 + 1][a2] = a4;
				Q.push(make_tuple(a1 + 1, a2, V[a1 + 1][a2]));
			}
		}
		if (a2 - 1 >= 0) {
			int a4 = X[a1][a2 - 1];
			a4 = max(a4, a3);
			if (V[a1][a2 - 1]>a4) {
				V[a1][a2 - 1] = a4;
				Q.push(make_tuple(a1, a2 - 1, V[a1][a2 - 1]));
			}
		}
		if (a2 + 1 < W) {
			int a4 = X[a1][a2 + 1];
			a4 = max(a4, a3);
			if (V[a1][a2 + 1]>a4) {
				V[a1][a2 + 1] = a4;
				Q.push(make_tuple(a1, a2 + 1, V[a1][a2 + 1]));
			}
		}
	}
	if (V[SX][SY] >= 2000) {
		cout << "-1" << endl;
	}
	else {
		cout << V[SX][SY] << endl;
	}
	return 0;
}