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

using namespace std;

const int N = 1000;
const int INF = 100000000;

class State{
public:
  int y, x, t;
  State(int y, int x, int t) : y(y), x(x), t(t) {}
};

int w, h, n, x, y, data[N][N], vis[N][N], dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}, ny, nx, gx, gy;
char mapd[N][N];

int solve(){
  fill(vis[0], vis[N], INF);
  vis[0][0] = 0;
  State u = State(0, 0, 0);
  queue<State> q;
  q.push(u);
  while(!q.empty()){
    u = q.front(); q.pop();
    for(int i=0;i<4;i++){
      ny = u.y + dy[i];
      nx = u.x + dx[i];
      if(0 <= ny && ny < h && 0 <= nx && nx < w){
        State v = State(ny, nx, u.t);
        if(mapd[ny][nx] == '#'){
          if(data[ny][nx] == 0) continue;
          if(data[ny][nx] > u.t) v.t = data[ny][nx];
        }
        if(vis[ny][nx] > v.t){
          vis[ny][nx] = v.t;
          q.push(v);
        }
      }
    }
  }
  return vis[gy][gx] == INF ? -1 : vis[gy][gx];
}

int main(){
  cin >> w >> h;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> mapd[i][j];
      if(mapd[i][j] == 't'){
        gy = i;
        gx = j;
        mapd[i][j] = '.';
      }
    }
  }
  cin >> n;
  fill(data[0], data[N], 0);
  for(int i=1;i<=n;i++){
    cin >> x >> y;
    data[y][x] = i;
  }
  cout << solve() << endl;
}