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
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int M = 2010;
char T[M][M];

int Q[M*M];
int D[M*M];

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

int main() {
    int n,m,k;

    scanf("%d%d%d", &n,&m,&k);

    for (int i=0;i<n;i++) {
        scanf("%s", T[i]);
    }
 
    Q[0]=0;
    D[0]=1;
    int a = 0, b = 1;
    int d;
    while (a < b) {
        int v=Q[a++];
        int ay = v/M;
        int ax = v%M;
        if (ay == (n-1) && ax == (m-1)) {
            d = D[v]; break;
        }
        for (int i=0;i<4;i++) {
            int nx = ax + dx[i];
            int ny = ay + dy[i];
            if (nx >=0 && nx < m && ny >= 0 && ny < n && T[ny][nx] == '.') {
                int ee = ny * M + nx;
                if (!D[ee]) {
                    Q[b++]=ee;
                    D[ee] = D[v]+1;
                }
            }
        }
    }
    d--;
    
    ll h = (d - (n + m - 2)) / 2;
    ll ma = (n + m - 2) + h;

    ll bsf = 100000000000000000L;
    int cbsf = 0;
    int c1, c2;

    for (int i=0; i<k;i++) {
        scanf("%d%d", &c1, &c2);
        ll cv = ma * c1 + h * c2;
        if (cv < bsf) {
            bsf = cv;
            cbsf = 1;
        } else if (cv == bsf) {
            cbsf++;
        }
    }
    
    printf("%lld %d\n", bsf, cbsf);
    return 0;
 
}