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 <cstring>
#include <queue>
#include <algorithm>
#include <string>
#include <cstdio>

using namespace std;

int f[1001][1001];
bool checked[1001][1001];
int gx,gy,n;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
int w,h;
bool solve(int hour){
    memset(checked, false,sizeof(checked));
    deque<pair<int,int> > q;
    pair<int,int> tmp;
    int nx,ny;
    q.push_back(make_pair(0,0));
    checked[0][0] = true;
    while(!q.empty()){
        tmp = q.front();
        q.pop_front();
        if(tmp.first == gx && tmp.second == gy){
            return true;
        }

        for(int i=0;i<4;i++){
            nx = tmp.first + dx[i];
            ny = tmp.second + dy[i];
            if(0 <= nx && nx < w &&
               0 <= ny && ny < h &&
               f[ny][nx] != -1 &&
               f[ny][nx] <= hour &&
               !checked[ny][nx]){
                q.push_back(make_pair(nx,ny));
                checked[ny][nx] = true;
            }
        }
    }
    return false;
}

int main(){
    int x,y;
    char c;

    cin >> w >> h;

    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin >> c;
            if(c == '.'){
                f[i][j] = 0;
            }else if(c == '#'){
                f[i][j] = -1;
            }else if(c == 't'){
                gx = j;
                gy = i;
                f[i][j] = 0;
            }
        }
    }
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> x >> y;
        f[y][x] = i+1;
    }

    int lb = 0, ub = 2000,mid;
    if(solve(0)) ub = 0;
    while(ub - lb > 1){
        mid = (lb+ub)/2;
        if(solve(mid)){
            ub = mid;
        }else{
            lb = mid;
        }
    }

    if(ub > n){
        cout << -1 << endl;
    }else{
        cout << ub << endl;
    }
}