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
107
108
#include <iostream>
#include <queue>
#include <climits>

using namespace std;

const int N = 1 << 11;
const int K = 1 << 20;

int n, m, k;
char A[N][N];
int Cnd[K][2];
int Dist[N][N][2];
bool Vis[N][N];

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void bfs(int x, int y) {
    queue<pair<int, int> > Q;
    Q.push(make_pair(x, y));
    Dist[x][y][0] = 0;
    Dist[x][y][1] = 0;
    Vis[x][y] = 1;
    
    while (!Q.empty()) {
        int sz = Q.size();
    
        for (int i=0; i<sz; i++) {
            x = Q.front().first;
            y = Q.front().second;
            Q.pop();
            
            for (int j=0; j<2; j++) {
                if (!Vis[x+dx[j]][y+dy[j]] && A[x+dx[j]][y+dy[j]] == '.') {
                    Vis[x+dx[j]][y+dy[j]] = 1;
                    Dist[x+dx[j]][y+dy[j]][0] = Dist[x][y][0] + 1;
                    Dist[x+dx[j]][y+dy[j]][1] = Dist[x][y][1];
                    
                    Q.push(make_pair(x+dx[j], y+dy[j]));
                }
            }
            
            for (int j=2; j<4; j++) {
                if (!Vis[x+dx[j]][y+dy[j]] && A[x+dx[j]][y+dy[j]] == '.') {
                    Vis[x+dx[j]][y+dy[j]] = 1;
                    Dist[x+dx[j]][y+dy[j]][0] = Dist[x][y][0];
                    Dist[x+dx[j]][y+dy[j]][1] = Dist[x][y][1] + 1;                
                    Q.push(make_pair(x+dx[j], y+dy[j]));    
                }
            }
        }
    }
}

void init() {
   cin >> n >> m >> k;
    
   for (int i=1; i<=n; i++) {
       for (int j=1; j<=m; j++) {
           cin >> A[i][j];
      }
   }
    
   for (int i=0; i<k; i++) {
       cin >> Cnd[i][0] >> Cnd[i][1];
   }
    
   for (int i=0; i<=n+1; i++) {
       Vis[i][0] = 1;
       Vis[i][m+1] = 1;
   }
        
   for (int i=0; i<=m+1; i++) {
       Vis[0][i] = 1;
       Vis[n+1][i] = 1; 
   }
}

void solve() {
   bfs(1, 1); 
    
   long long mini = LLONG_MAX - 1;
   int cnt = 0; 

   for (int i=0; i<k; i++) {
       mini = min(mini, (long long)Dist[n][m][0] * Cnd[i][0] + (long long)Dist[n][m][1] * Cnd[i][1]); 
   }
    
   for (int i=0; i<k; i++) {
       if ((long long)Dist[n][m][0] * Cnd[i][0] + (long long)Dist[n][m][1] * Cnd[i][1] == mini) {
           cnt++;
       }
   }
    
   cout << mini << ' ' << cnt << '\n';                
}

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

    init();
    solve();

    return 0;
}