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

using namespace std;

#define D(x)

#define MAX 2022
#define MAX2 1000100

typedef long long I;

char M[MAX][MAX];
I M2[MAX][MAX];
I a[MAX2], b[MAX2];
int n,m,k;

void printM() {
    for(int i=0;i<=n+1;i++) {
        for(int j=0;j<=m+1;j++) printf("%c", M[i][j]);
        printf("\n");
    }
}

struct V {
    int x,y;
    I k;
};

V kier[] = {{0,1, -2000000}, {0,-1, -1} , {1,0, -2000000}, {-1, 0, -1}};

int main()
{
    scanf("%d %d %d", &n ,&m, &k);
    for(int i=1;i<=n;i++) scanf(" %s", &M[i][1]);
    for(int i=0;i< k;i++) scanf("%lld %lld", &a[i], &b[i]);
    
    for(int i=0;i<=m+1;i++) M[n+1][i] = M[0][i] = 'X';
    for(int i=0;i<=n+1;i++) M[i][0] = M[i][m+1] = 'X';

    D(printM());
    queue<V> q;
    q.push(V{1,1,0});
    M[1][1]= 'X';
    while(!q.empty()) {
        auto p = q.front();
        q.pop();
        for(auto v : kier) {
            V np = {p.x + v.x, p.y + v.y, 0};
            if(M[np.x][np.y] != 'X')  {
                M2[np.x][np.y] = min(M2[np.x][np.y], M2[p.x][p.y] + v.k);
                M[np.x][np.y] = 'X';
                q.push(np);
            }
        }
    }
    I aa = -M2[n][m] / 2000000, bb = (-M2[n][m])%2000000;
    D(cout << aa << " " << bb << "\n");
    I sm = LLONG_MAX, c = 0;
    for(int i=0;i<k;i++) {
        a[i] = a[i]*aa + b[i]*bb;
        sm = min(sm, a[i]);
    }
    for(int i=0;i<k;i++) if(a[i]==sm) c++;
    cout << sm << " " << c << "\n";

    
    
}