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

constexpr int nax = 2000, maxm = nax, kax = 1e6, pax = nax * maxm, inf = 1e9;
constexpr int64_t llinf = 1e18;

int n, m, k;
int odl[nax + 1][maxm + 1];
bool gr[nax + 1][maxm + 1];
const array< int, 2 > jaf[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;

    for (int i = 1; i <= n; ++i) {
        string s; cin >> s;
        for (int j = 1; j <= m; ++j) {
            gr[i][j] = (s[j - 1] == '.');
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            odl[i][j] = inf;
        }
    }

    deque< array< int, 2 > > dq;
    odl[1][1] = 0;
    dq.push_front({1, 1});

    while (not dq.empty()) {
        auto v = dq.front(); dq.pop_front();
        for (auto s : jaf) {
            auto nv = v;
            nv[0] += s[0]; nv[1] += s[1];
            int nodl = odl[v[0]][v[1]] + (s[0] + s[1] > 0? 0 : 1);
            if (gr[nv[0]][nv[1]] and odl[nv[0]][nv[1]] > nodl) {
                odl[nv[0]][nv[1]] = nodl;
                if (s[0] + s[1] > 0)
                    dq.push_front(nv);
                else
                    dq.push_back(nv);
            }
        }
    }

    int l = odl[n][m];
    int r = odl[n][m] + (n - 1) + (m - 1);

    int cnt = 0;
    int64_t res = llinf;
    for (int i = 0; i < k; ++i) {
        int a, b; cin >> a >> b;
        int64_t v = ((int64_t)b * l + (int64_t)a * r);
        if (v < res) res = v, cnt = 1;
        else if (v == res) ++cnt;
    }

    cout << res << ' ' << cnt << '\n';
}