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
 97
 98
 99
100
101
102
#include <cstdio>
#include <queue>

using namespace std;

const int N = 2001;

char a[N][N];

long long INF = 1LL << 62;
long long large_edge = 1 << 30;
long long dist[N][N];
int n, m;

void calc_dist()
{
  priority_queue< pair<long long, pair<int, int>>, vector<pair<long long, pair<int, int>>>, greater<pair<long long, pair<int, int>>>> pq;
  for(int i = 1; i <= n; i++)
  {
    for(int j = 1; j <= m; j++)
    {
      dist[i][j] = INF;
    }
  }
      
  dist[1][1] = 0;
  pq.push({0, {1, 1}});
  while(pq.size())
  {
      pair<int, int> u = pq.top().second;
      long long du = pq.top().first;
      pq.pop();
      if (du != dist[u.first][u.second]) continue;
      
      long long w = 1;
      int v = u.first + 1;
      if (v <= n && du + w < dist[v][u.second] && a[v][u.second] == '.')
      {
        dist[v][u.second] = du + w;
        pq.push({dist[v][u.second], {v, u.second}});
      }

      w = large_edge;
      v = u.first - 1;
      if (v >= 1 && du + w < dist[v][u.second] && a[v][u.second] == '.')
      {
        dist[v][u.second] = du + w;
        pq.push({dist[v][u.second], {v, u.second}});
      }

      w = 1;
      v = u.second + 1;
      if (v <= m && du + w < dist[u.first][v] && a[u.first][v] == '.')
      {
        dist[u.first][v] = du + w;
        pq.push({dist[u.first][v], {u.first, v}});
      }

      w = large_edge;
      v = u.second - 1;
      if (v >= 1 && du + w < dist[u.first][v]&& a[u.first][v] == '.')
      {
        dist[u.first][v] = du + w;
        pq.push({dist[u.first][v], {u.first, v}});
      }
  }
}

int main()
{
  int k;
  scanf("%d %d %d",&n,&m, &k);
  for (int i = 1; i <= n; i++)
  {
    scanf("%s", &a[i][1]);
  }
  
  calc_dist();

  long long x = dist[n][m] % large_edge, y = dist[n][m] / large_edge;
  long long m = INF;
  int cnt = 0;

  for (int i = 0; i < k; i++)
  {
    int a, b;
    scanf("%d %d", &a, &b);

    if (x * a + y * b < m)
    {
      m = x * a + y * b;
      cnt = 1;
    }
    else if (x * a + y * b == m)
    {
      cnt++;
    }
  }
  
  printf("%lld %d\n", m, cnt);
  return 0;
}