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 <string>
#include <cmath>
#include <queue>
using namespace std;

const int MAX_W = 1000;
const int INF = 1000000;
char map[MAX_W][MAX_W];
int costs[MAX_W][MAX_W];
int times[MAX_W][MAX_W];

int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
struct State {
  int x;
  int y;
  int cost;
  State(int x, int y, int cost) : x(x), y(y), cost(cost) {}
  const bool operator< (const State& other) const {
    return cost > other.cost;
  }
  const bool operator> (const State& other) const {
    return cost < other.cost;
  }
};
int main() {
  int w, h;
  cin >> w >> h;
  for (int i = 0; i < h; i++) {
//    cin >> map[i];
    for (int j = 0; j < w; j++) {
      cin >> map[i][j];
      costs[i][j] = INF;
      times[i][j] = INF;
    }
  }
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x, y;
    cin >> x >> y;
    times[y][x] = min(times[y][x], i);
  }
  priority_queue<State> pq;
  pq.push(State(0, 0, 0));
  while (!pq.empty()) {
    State s = pq.top();
    pq.pop();
    if (costs[s.y][s.x] != INF) {
      continue;
    }
    
    costs[s.y][s.x] = s.cost;
//    cout << "cost=" << s.cost << ", xy=" << s.x << "," << s.y << endl;
    for (int i = 0; i < 4; i++) {
      int nextX = s.x + dx[i];
      int nextY = s.y + dy[i];
      if (0 <= nextX && nextX < w && 0 <= nextY && nextY < h) {
        if (map[nextY][nextX] == 't') {
          cout << s.cost << endl;
          return 0;
        }
        int time = map[nextY][nextX] == '#' ? times[nextY][nextX] : 0;
        int cost = max(time, s.cost);
        if (cost != INF) {
  //        cout << "push:" << cost << ", "<< i<<endl;
          pq.push(State(nextX, nextY, cost));
        }
      }
    }
  }
  cout << -1 << endl;
  return 0;
}