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

using namespace std;

int n, m, k;
vector<string> v;
vector<int> from;
vector<pair<long long, long long> > speed;

int X[4] = {1, -1, 0, 0};
int Y[4] = {0, 0, 1, -1};

bool inbounds(const int& x, const int& y)
{
  if (x < 0 || y < 0 || x >= n || y >= m)
    return false;
  return v[x][y] == '.';
}

void bfs()
{
  from.assign(n * m, -1);
  from[0] = 0;
  queue<int> q;
  q.push(0);
  while (!q.empty())
  {
    pair<int, int> top = make_pair(q.front() / m, q.front() % m);
    for (int i = 0; i < 4; i++)
    {
      int x = top.first + X[i], y = top.second + Y[i];
      if (inbounds(x, y) && from[x * m + y] == -1)
      {
        from[x * m + y] = q.front();
        q.push(x * m + y);
      }
    }
    q.pop();
  }
  long long up = 0, down = 0;
  for (int i = n * m - 1; i > 0; i = from[i])
    ++(from[i] > i ? down : up);
  
  long long fastest = 1000000000000000001;
  for (pair<long long, long long>& i : speed)
    fastest = min(fastest, i.first * up + i.second * down);
  int count = 0;
  for (pair<long long, long long>& i : speed)
    count += fastest == i.first * up + i.second * down;
  cout << fastest << ' ' << count << '\n';
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n >> m >> k;
  v.resize(n);
  for (string& s : v)
    cin >> s;
  speed.resize(k);
  for (pair<long long, long long>& i : speed)
    cin >> i.first >> i.second;

  bfs();
}