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

#define fi first
#define se second
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 2005;

int n, m;
char in[maxn][maxn];
bool vis[maxn][maxn];

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

int main()
{
    ios_base::sync_with_stdio(0);
    
    int k;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> in[i][j];
        }
    }

    queue<pair<pii, pii> > Q;

    pii droga;

    Q.push({{0, 0}, {0, 0}});
    while(!Q.empty()) {
        auto v = Q.front(); Q.pop();

        if (v.fi.fi == n - 1 && v.fi.se == m - 1) {
            droga = v.se;
            break;
        }

        if (vis[v.fi.fi][v.fi.se])
            continue;
        vis[v.fi.fi][v.fi.se] = true;

        for (int i = 0; i < 4; i++) {
            int nx = v.fi.fi + dx[i];
            int ny = v.fi.se + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;
            if (in[nx][ny] == 'X')
                continue;
            int gora = 0, dol = 0;
            if (dx[i] > 0 || dy[i] > 0)
                gora++;
            else
                dol++;
            
            Q.push({{nx, ny}, {v.se.fi + gora, v.se.se + dol}});
        }
    }

    //cout << droga.fi << " " << droga.se << "\n";

    ll best = 1e18;
    int bestcnt = 0;

    for (int i = 0; i < k; i++) {
        ll a, b;
        cin >> a >> b;

        ll czas = a * droga.fi + b * droga.se;
        if (czas < best) {
            best = czas;
            bestcnt = 1;
        } else if (czas == best) {
            bestcnt++;
        }
    }

    cout << best << " " << bestcnt << "\n";

    return 0;
}