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


using namespace std;


const long long INF = 1LL << 60;


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


int main() {
    ios_base::sync_with_stdio(false);

    int n, m, k;
    cin >> n >> m >> k;

    vector <string> tab(n);
    for (auto &s : tab) {
        cin >> s;
    }

    vector <vector<int>> distUp(n, vector <int> (m, -1));
    vector <vector<int>> distDown(n, vector <int> (m, -1));

    distUp[0][0] = distDown[0][0] = 0;

    queue <pair<int,int>> q;
    q.push({0, 0});

    while (!q.empty()) {
        int x, y;
        tie(x, y) = q.front(); q.pop();

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir], ny = y + dy[dir];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && tab[nx][ny] == '.' && distUp[nx][ny] == -1) {
                bool up = dir < 2;

                distUp[nx][ny] = distUp[x][y] + up;
                distDown[nx][ny] = distDown[x][y] + !up;

                q.push({nx, ny});
            }
        }
    }

    long long minTime = INF;
    int numPeople = 0;

    while (k--) {
        int timeUp, timeDown;
        cin >> timeUp >> timeDown;

        long long time = (long long) timeUp * distUp[n-1][m-1] + (long long) timeDown * distDown[n-1][m-1];

        if (time < minTime) {
            minTime = time;
            numPeople = 1;
        } else if (time == minTime) {
            numPeople++;
        }
    }

    cout << minTime << ' ' << numPeople << '\n';

    return 0;
}