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<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<queue>

using namespace std;

typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef long long LL;

#define FOR(x, b, e) for(int x=b; x<=(e); ++x)
#define FORD(x, b, e) for(int x=b; x>=(e); --x)
#define REP(x, n) for(int x=0; x<(n); ++x)
#define VAR(v, n) __typeof(n) v = (n)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) ((int)(x).size())
#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define PB push_back
#define ST first
#define ND second
#define MP make_pair

const int INF = 1000000001;

int n, m, k;
vector<string> area;

void findRoutes(VVI &routes, int i, int j) {
    queue<pair<int, int> > q;
    q.push(MP(i, j));
    while(!q.empty()) {
        int i = q.front().ST;
        int j = q.front().ND;
        q.pop();
        if(i - 1 >= 0 && routes[i-1][j] > routes[i][j] + 1 && area[i-1][j] == '.') {
            routes[i-1][j] = 1 + routes[i][j];
            q.push(MP(i-1, j));
        }
        if(i + 1 < n && routes[i+1][j] > routes[i][j] + 1 && area[i+1][j] == '.') {
            routes[i+1][j] = 1 + routes[i][j];
            q.push(MP(i+1, j));
        }
        if(j - 1 >= 0 && routes[i][j-1] > routes[i][j] + 1 && area[i][j-1] == '.') {
            routes[i][j-1] = 1 + routes[i][j];
            q.push(MP(i, j-1));
        }
        if(j + 1 < m && routes[i][j+1] > routes[i][j] + 1 && area[i][j+1] == '.') {
            routes[i][j+1] = 1 + routes[i][j];
            q.push(MP(i, j+1));
        }
    }
}

int main() {
	ios_base::sync_with_stdio(0);
    cin >> n >> m >> k;
    area.resize(n);
    REP(i, n) {
        cin >> area[i];
    }
    VVI routes(n, VI(m, INF));
    routes[n-1][m-1] = 0;
    findRoutes(routes, n-1, m-1);
    int i=0, j=0, up=0, down=0;
    while(i != n-1 || j != m-1) {
        if (j+1 < m && routes[i][j+1] < routes[i][j]) { j++; up++; }
        else if(i+1 < n && routes[i+1][j] < routes[i][j]) { i++; up++; }
        else if(j-1 >= 0 && routes[i][j-1] < routes[i][j]) { j--; down++; }
        else if(i-1 >= 0 && routes[i-1][j] < routes[i][j]) { i--; down++; }
    }
    LL time = -1;
    int count = 0;
    REP(i, k) {
        LL a, b;
        cin >> a >> b;
        LL t = a * up + b * down;
        if(time < 0 || t < time) {
            time = t;
            count = 1;
        } else if(time == t) count++;
    }
    cout << time << ' ' << count << '\n';
    return 0;
}