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

using namespace std;

string mapa[2002];

#define OK 0
#define X 1

typedef pair<long long,long long> II;

int main()
{
    std::ios::sync_with_stdio(0);

    long long i, n, m, k;

    cin >> n >> m >> k;
    
    mapa[0].resize(m+2);
    mapa[n+1].resize(m+2);
    for (i=0; i<=m+1; i++)
    {
      mapa [0]  [i] = 'X';
      mapa [n+1][i] = 'X';
    }  
      
    for (i=1; i<=n; i++)
    {
      string s;
      cin >> s;
      mapa [i] = "X" + s + "X";
    }  

    vector<long long> a(k), b(k);
    
    for (i=0; i<k; i++)
      cin >> a[i] >> b[i];
      
    vector<vector<long long> > dist(n+2, vector<long long>(m+2,-1)) ; 
    
    dist[1][1] = 0;
    
    queue<II> q;
    
    q.push(II(1,1));  
    
    while (!q.empty())
    {
      II v = q.front();
      q.pop();
      
      long long i = v.first;
      long long j = v.second;
      
      if (i == n && j == m)
        break;
      
      if (dist[i-1][j] == -1 && mapa[i-1][j] == '.')
      {
        dist[i-1][j] = dist[i][j] + 1;
        q.push(II(i-1,j));
      }  

      if (dist[i+1][j] == -1 && mapa[i+1][j] == '.')
      {
        dist[i+1][j] = dist[i][j] + 1;
        q.push(II(i+1,j));
      }  

      if (dist[i][j-1] == -1 && mapa[i][j-1] == '.')
      {
        dist[i][j-1] = dist[i][j] + 1;
        q.push(II(i,j-1));
      }  

      if (dist[i][j+1] == -1 && mapa[i][j+1] == '.')
      {
        dist[i][j+1] = dist[i][j] + 1;
        q.push(II(i,j+1));
      }  
    }
    
    long long t = (dist[n][m] - n - m + 2) / 2;
    
    long long best = (n+m-2)*a[0] + t*(a[0]+b[0]);
    long long cnt = 0;
    
    for (i=0; i<k; i++)
    {
      long long time = (n+m-2)*a[i] + t*(a[i]+b[i]);
      if (time == best)
        cnt++;
      else
        if (time < best)
        {
          cnt = 1;
          best = time;
        }
    }
    
    cout << best << " " << cnt << "\n";
 

    return 0;
}