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
89
90
91
92
93
94
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

struct pole {
	bool valid;
	int dist;
	int pen;
};

#define IX(r,c)	((r) * ((m)+2) + (c))

#define DUMP do { \
	cout << "*******************\n"; \
	for(int i = 0; i <= n+1; ++i) { \
		for(int j = 0; j <= m+1; ++j) { \
			cout << ((t[IX(i,j)].valid)?".":"X"); \
		} \
		for(int j = 0; j <= m+1; ++j) { \
			cout << "\t" << (t[IX(i,j)].dist); \
		} \
		cout << "\n"; \
	} \
} while(0); \

#define LEFT(ix)	((ix) - 1)
#define RIGHT(ix)	((ix) + 1)
#define UP(ix)		((ix) - m - 2)
#define DOWN(ix)	((ix) + m + 2)

#define DO(iy, ip) do { \
	if((t[iy].dist < 0) && (t[iy].valid)) { \
		t[iy].dist = t[i].dist + 1; \
		t[iy].pen = t[i].pen + ip; \
		q[qe++]=iy; \
	} \
} while (0); \

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio (false);
	int n, m, k, i, j;
	cin >> n >> m >> k;
	vector<pole> t((n+2)*(m+2));
	string s;
	for (i = 1; i <= n; ++i) {
		cin >> s;
		for (j = 1; j <= m; ++j) {
			t[IX(i,j)] = pole{(s[j-1] == '.'), -1, -1};
		}
	}
	for (i = 0; i <= n+1; ++i) {
		t[IX(i,0)] = pole{false, -1, -1};
		t[IX(i,m+1)] = pole{false, -1, -1};
	}
	for (j = 1; j <= m; ++j) {
		t[IX(0,j)] = pole{false, -1, -1};
		t[IX(n+1,j)] = pole{false, -1, -1};
	}
	t[IX(1,1)].dist=0;
	t[IX(1,1)].pen=0;
//	DUMP

	vector<int> q((n+2)*(m+2));
	int qb=0, qe=0, tgt=IX(n,m);
	q[qe++]=IX(1,1);
	while(1) {
		i = q[qb++];
		if (i == tgt)
			break;
		DO(LEFT(i), 1);
		DO(RIGHT(i), 0);
		DO(UP(i), 1);
		DO(DOWN(i), 0);
	}
//	DUMP
	int64_t c = n + m - 2 + t[tgt].pen;
	int64_t d = t[tgt].pen;
	int64_t a, b, M=INT64_MAX, Q=0, T;
	for (i = 0; i < k; ++i) {
		cin >> a >> b;
		T = a * c + b * d;
		if (T < M) {
			M = T;
			Q = 1;
		} else if (T == M) {
			Q++;
		}
	}

	cout << M << " " << Q << "\n";
}