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

using namespace std;

#define JOIN_(X, Y) X##Y
#define JOIN(X, Y) JOIN_(X, Y)
#define TMP JOIN(tmp, __LINE__)
#define PB push_back
#define SZ(x) int((x).size())
#define REP(i, n) for (int i = 0, TMP = (n); i < TMP; ++i)
#define FOR(i, a, b) for (int i = (a), TMP = (b); i <= TMP; ++i)
#define FORD(i, a, b) for (int i = (a), TMP = (b); i >= TMP; --i)

#ifdef DEBUG
#define DEB(x) (cerr << x)
#else
#define DEB(x)
#endif

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

const int INF = 1e9 + 9;

vector<string> t;
vector<vi> dist;

void inline one() {
    int n, m, k;
    cin >> n >> m >> k;
    REP(i, n) {
        string s;
        cin >> s;
        t.PB(s);
        dist.PB(vi(m, INF));
    }
    // BFS:
    queue<pii> q;
    dist[0][0] = 0;
    q.push(pii(0, 0));
    while (!q.empty()) {
        pii xy = q.front();
        int x = xy.first;
        int y = xy.second;
        q.pop();
        FOR(dx, -1, 1) {
            FOR(dy, -1, 1) {
                if ((dx == 0 && dy != 0) || (dx != 0 && dy == 0)) {
                    int nx = x + dx;
                    int ny = y + dy;
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                        if (t[x][y] == '.' && dist[x][y] + 1 < dist[nx][ny]) {
                            dist[nx][ny] = dist[x][y] + 1;
                            q.push(pii(nx, ny));
                        }
                    }
                }
            }
        }
    }
    int target_dist = dist[n - 1][m - 1];
    int min_dist = (n - 1) + (m - 1);
    int up = min_dist + (target_dist - min_dist) / 2;
    int down = (target_dist - min_dist) / 2;
    ll best = 1e18;
    int best_count = 0;

    REP(i, k) {
        int cost_up, cost_down;
        cin >> cost_up >> cost_down;
        ll total_cost = (ll)(cost_up)*up + (ll)(cost_down)*down;
        if (total_cost < best) {
            best = total_cost;
            best_count = 1;
        } else if (total_cost == best) {
            ++best_count;
        }
    }
    cout << best << " " << best_count << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // int z; cin >> z; while(z--)
    one();
}