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

using namespace std;

const int N = 2002;
int used[N][N];

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

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<string> f(n);
    for (int i = 0; i < n; i++) {
        cin >> f[i];
    }
    memset(used, 255, sizeof(used));
    deque<pair<int, int> > q;
    q.push_back({0,0});
    used[0][0] = 0;
    while (!q.empty()) {
        auto p = q.front();
        q.pop_front();
        int x = p.first;
        int y = p.second;
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (f[nx][ny] == '.' && used[nx][ny] == -1) {
                    used[nx][ny] = used[x][y] + 1;
                    q.push_back({nx, ny});
                }
            }
        }
    }
    int dist = used[n-1][m-1];
    int up = n-1 + m-1;
    int rest = dist - up;
    up += rest / 2;
    int down = rest / 2;

    long long ans = 1e18;
    int cnt = 0;
    for (int j = 0; j < k; j++) {
        int a, b;
        cin >> a >> b;
        long long cand = 1LL * a*up + 1LL * b*down;
        if (cand < ans) {
            ans = cand;
            cnt = 1;
        } else if (cand == ans) {
            cnt++;
        }
    }

    cout << ans << " " << cnt << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cout.precision(12);
    cout << fixed;
    cin.tie(0);

    int T = 1;
    //cin >> T;
    for (int t = 0; t < T; t++) {
        solve();
    }

    return 0;
}