1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Node {
  bool vis;
  int top;
  int bottom;
};

int n, m;

void bfs(vector<vector<Node>> &G, pair<int, int> start) {
  queue<pair<int, int>> q;
  q.push(start);
  G[start.first][start.second].top = 0;
  G[start.first][start.second].bottom = 0;

  while(!q.empty()) {
    pair<int, int> curr = q.front();
    q.pop();

    if(curr.first == n && curr.second == m) {
      return;
    }

    // top
    if(G[curr.first - 1][curr.second].vis && G[curr.first - 1][curr.second].bottom == -1) {
      G[curr.first - 1][curr.second].bottom = G[curr.first][curr.second].bottom + 1;
      G[curr.first - 1][curr.second].top = G[curr.first][curr.second].top;
      q.push({curr.first - 1, curr.second});
    }

    // left
    if(G[curr.first][curr.second - 1].vis && G[curr.first][curr.second - 1].bottom == -1) {
      G[curr.first][curr.second - 1].bottom = G[curr.first][curr.second].bottom + 1;
      G[curr.first][curr.second - 1].top = G[curr.first][curr.second].top;
      q.push({curr.first, curr.second - 1});
    }

    // right
    if(G[curr.first][curr.second + 1].vis && G[curr.first][curr.second + 1].bottom == -1) {
      G[curr.first][curr.second + 1].top = G[curr.first][curr.second].top + 1;
      G[curr.first][curr.second + 1].bottom = G[curr.first][curr.second].bottom;
      q.push({curr.first, curr.second + 1});
    }

    // bottom
    if(G[curr.first + 1][curr.second].vis && G[curr.first + 1][curr.second].bottom == -1) {
      G[curr.first + 1][curr.second].top = G[curr.first][curr.second].top + 1;
      G[curr.first + 1][curr.second].bottom = G[curr.first][curr.second].bottom;
      q.push({curr.first + 1, curr.second});
    }
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int k; cin >> n >> m >> k;
  vector<vector<Node>> G(n + 2, vector<Node>(m + 2));

  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      char c; cin >> c;
      G[i][j].vis = c == '.';
      G[i][j].bottom = -1;
    }
  }

  bfs(G, {1, 1});

  long long top = G[n][m].top, bottom = G[n][m].bottom;

  long long min = LONG_LONG_MAX;
  int ans = 0;
  while(k--) {
    int a, b; cin >> a >> b;
    long long curr = (long long)(top * a) + (long long)(bottom * b);
    if(curr < min) {
      min = curr;
      ans = 1;
    }
    else if(curr == min) {
      ans++;
    }
  }

  cout << min << " " << ans << "\n";

  return 0;
}