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 <map>
#include <vector>
#include <algorithm>
using namespace std;

int v[1001][1001];

int done[1000][1000] = {};

struct NODE{
	int x,y,c;
	NODE(int x,int y,int c) : x(x) , y(y) , c(c) {}
};
bool operator < (const NODE &a,const NODE &b){
	return a.c > b.c;
}

int main(){
	int H,W;
	cin >> W >> H;
	int gx,gy;
	for(int i = 0 ; i < H ; i++){
		for(int j = 0 ; j < W ; j++){
			char c;cin >> c;
			if( c == 't' ){
				gx = j;
				gy = i;
				v[i][j] = 0;
			}else if( c == '#' ) v[i][j] = 1e9;
			else v[i][j] = 0;
		}
	}
	int n;
	cin >> n;
	
	for(int i = 1 ; i <= n ; i++){
		int x,y;
		cin >> x >> y;
		v[y][x] = i;
	}
	priority_queue<NODE> Q;
	Q.push(NODE(0,0,0));
	int dx[] = {-1,0,1,0};
	int dy[] = {0,1,0,-1};
	
	while(Q.size()){
		NODE q = Q.top(); Q.pop();
		if( q.c == 1e9 ) continue;
		if( q.y == gy && q.x == gx ) {
			cout << q.c << endl;
			return 0;
		}
		if( done[q.y][q.x]++ ) continue;
		for(int i = 0 ; i < 4 ; i++){
			int tx = q.x + dx[i];
			int ty = q.y + dy[i];
			if( tx < 0 || ty < 0 || tx >= W || ty >= H ) continue;
			Q.push(NODE(tx,ty,max(q.c,v[ty][tx])));
		}
	}
	cout << -1 << endl;
	
}