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

using namespace std;

#define MAX_N	2010
#define MAX_M	2010

int N, M, K;
int f[MAX_N][MAX_M];
queue<pair<int, int>> q;

void g() {
	while (!q.empty()) {
		pair<int, int> c = q.front();
		q.pop();

		int i = c.first;
		int j = c.second;

		if (i == N  - 1 && j == M - 1) {
			return;
		}

		if (i > 0 && f[i - 1][j] == 0) {
			f[i - 1][j] = f[i][j] + 1;
			q.push(make_pair(i - 1, j));
		}
		if (j > 0 && f[i][j - 1] == 0) {
			f[i][j - 1] = f[i][j] + 1;
			q.push(make_pair(i, j - 1));
		}
		if (i < N - 1 && f[i + 1][j] == 0) {
			f[i + 1][j] = f[i][j] + 1;
			q.push(make_pair(i + 1, j));		
		}
		if (j < M - 1 && f[i][j + 1] == 0) {
			f[i][j + 1] = f[i][j] + 1;
			q.push(make_pair(i, j + 1));
		}		
	}
}

int main() {
	char r[MAX_M];
	int a, b;

	scanf("%d %d %d", &N, &M, &K);

	for (int i = 0; i < N; ++i) {
		scanf("%s", r);
		for (int j = 0; j < M; ++j) {
			if (r[j] == 'X') {
				f[i][j] = -1;
			}
		}
	}

	f[0][0] = 1;
	q.push(make_pair(0, 0));
	g();

	long long u = N + M - 2 + (f[N - 1][M - 1] - N - M + 1) / 2;
	long long d = u - N - M + 2;
	long long m = 0;
	int c = 0;

	for (int i = 0; i < K; ++i) {
		scanf("%d %d", &a, &b);
		long long t = u * a + d * b;

		if (m == 0 || t < m) {
			m = t;
			c = 1;
		} else if (t == m) {
			c++;
		}
	}

	printf("%lld %d\n", m, c);
	return 0;
}