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

void enqueueValid(queue<pair<int,int>>& Q, vector<vector<char>>& grid, int x, int y) {
    if(grid[x][y] == '.') {
        Q.push({x,y});
        grid[x][y] = 'X';
    }
}

int BFS(vector<vector<char>>& grid, int x, int y, int n, int m) {
    queue<pair<int,int>> Q;
    Q.push({x,y});
    int steps = 0;
    while(!Q.empty()) {
        int size = Q.size(); 
        while(size--) {
            pair<int,int> p = Q.front();
            Q.pop();
            x = p.first;
            y = p.second;
            if(x == n && y == m) {
                return steps;
            }

            enqueueValid(Q, grid, x-1, y);
            enqueueValid(Q, grid, x+1, y);
            enqueueValid(Q, grid, x, y-1);
            enqueueValid(Q, grid, x, y+1);
        }
        steps++;
    }
    return -1;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<char>> grid(n+2, vector<char>(m+2));
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }
    
    vector<pair<int,int>> speed(k);
    for(int i = 0; i < k; i++) {
        cin >> speed[i].first >> speed[i].second;
    }

    int totalSteps = BFS(grid, 1, 1, n, m);
    int ascSteps = n + m - 2 + (totalSteps - n - m + 2) / 2;
    int descSteps = totalSteps - ascSteps;
    
    long long int resTime = LONG_LONG_MAX;
    int resCount = 0;
    for(int i = 0; i < k; i++) {
        resTime = min(resTime, (long long)speed[i].first * ascSteps + (long long)speed[i].second * descSteps);
    }
    
    for(int i = 0; i < k; i++) {
        if(((long long)speed[i].first * ascSteps + (long long)speed[i].second * descSteps) == resTime) {
            resCount++;
        }
    }
    cout << resTime << " " << resCount << endl;
}