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
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<string> arr(n+2, string(m+2, 'X'));
  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < m; j++) {
      arr[i][j+1] = s[j];
    }
  }
  vector<vector<int>> d(n+2, vector<int>(m+2, -1));
  deque<pair<int, int>> Q;
  Q.push_back({1, 1});
  d[1][1] = 0;
  while (!Q.empty()) {
    auto v = Q.front();
    Q.pop_front();
    for (int i = -1; i <= 1; i++) {
      for (int j = -1; j <= 1; j++) {
        int x = v.first + i;
        int y = v.second + j;
        if (abs(i) + abs(j) == 1 && arr[x][y] == '.' && d[x][y] == -1) {
          d[x][y] = d[v.first][v.second] + 1;
          Q.push_back({x, y});
        }
      }
    }
  }
  int extra = d[n][m] - (n-1) - (m-1);
  pair<ll, int> res{1e18, 0};
  while (k--) {
    ll a, b;
    cin >> a >> b;
    ll w = a * (n-1 + m-1 + extra / 2) + b * (extra / 2);
    if (w < res.first) {
      res.first = w;
      res.second = 0;
    }
    if (w == res.first) {
      res.second++;
    }
  }
  cout << res.first << ' ' << res.second << endl;
}