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

using namespace std;
queue<pair<int,int>> q;
bool vis[2001][2001];
int tab[2001][2001];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,k; cin >> n >> m >> k;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            char a; cin >> a;
            tab[i][j] = INT_MAX-1;
            if(a == 'X')
                vis[i][j] = true;
        }
    }
    tab[0][0] = 0;
    q.push({0,0});
    while(q.size()){
        int i = q.front().first, j = q.front().second;
        q.pop();
        if(vis[i][j] == false){
            vis[i][j] = true;
            if(i > 0){
                tab[i][j] = min(tab[i][j],tab[i-1][j] + 1);
                q.push({i - 1, j});
            }
            if(j > 0){
                
                tab[i][j] = min(tab[i][j],tab[i][j-1] + 1);
                q.push({i, j - 1});
            }
            if(i < n-1){
                // cout << "B";
                tab[i][j] = min(tab[i][j],tab[i + 1][j] + 1);
                q.push({i + 1, j});
            }
            if(j < m-1){
                // cout << "A";
                tab[i][j] = min(tab[i][j],tab[i][j + 1] + 1);
                q.push({i, j + 1});
            }
        }
    }
    int res = tab[n-1][m-1] - n - m + 2;
    long long wyn = LLONG_MAX, ile = 0;
    while(k--){
        long long a,b; cin >> a >> b;
        long long res1 = ((n + m -2) * a) + (res/2 * a + res/2 * b);
        if(res1 == wyn){
            ile++;
        }
        if(res1 < wyn){
            ile = 1;
            wyn = res1;
        }
    }
    cout << wyn << " " << ile << "\n";

}