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

using namespace std;

#define rep(i, n) for (int i = 0; i < int(n); ++i)

const int INF = 1234567890;
typedef pair<int, pair<int, int> > data;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int main() {
  int w, h, n;
  cin >> w >> h;
  vector<string> mp(h);
  rep (i, h) cin >> mp[i];
  cin >> n;
  vector<vector<int> > open(h);
  rep (i, h) rep (j, w) {
    if (mp[i][j] == '#') open[i].push_back(INF);
    else open[i].push_back(0);
  }
  rep (i, n) {
    int x, y;
    cin >> x >> y;
    open[y][x] = i + 1;
  }
  vector<vector<int> > dis(h);
  rep (i, h) rep (j, w) dis[i].push_back(INF);
  priority_queue<data, vector<data>, greater<data> > que;
  que.push(make_pair(0, make_pair(0, 0)));
  while (!que.empty()) {
    data now = que.top();
    que.pop();
    if (dis[now.second.first][now.second.second] <= now.first) continue;
    dis[now.second.first][now.second.second] = now.first;
    //cout << now.second.first << " " << now.second.second << " " << now.first << endl;
    rep (i, 4) {
      data next = now;
      next.second.first += dy[i];
      next.second.second += dx[i];
      if (next.second.first < 0 || h <= next.second.first) continue;
      if (next.second.second < 0 || w <= next.second.second) continue;
      next.first = max(next.first, open[next.second.first][next.second.second]);
      que.push(next);
    }
  }
  int goalX, goalY;
  rep (i, h) rep (j, w) if (mp[i][j] == 't') {
    goalY = i;
    goalX = j;
  }
  if (dis[goalY][goalX] == INF) cout << -1 << endl;
  else cout << dis[goalY][goalX] << endl;
  return 0;
}