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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr int MAXNM = 2000;
constexpr int DY = 2048;
int v[(MAXNM + 2) * DY];

int main()
{
	int n, m, k;
	scanf("%d %d %d\n", &n, &m, &k);
	for (int i = 0; i < (n + 2) * DY; i++)
		v[i] = -1;
	char s[DY];
        for (int i = 0; i < n; i++) {
		scanf("%s\n", s);
		for (int j = 0; j < m; j++)
			if (s[j] == '.')
				v[(i + 1) * DY + j + 1] = MAXNM * DY;
	}
	v[DY + 1] = 0;
	deque<int> q;
	q.push_back(DY + 1);
	int t = n * DY + m;
        while (v[t] == MAXNM * DY) {
		int i = q.front();
		q.pop_front();
		int d = v[i] + 1;
                for (int dj : {-DY, -1, 1, DY}) {
			int j = i + dj;
                        if (d < v[j]) {
				v[j] = d;
				q.push_back(j);
			}
		}
	}
	ll x = n + m - 2;
	ll y = (v[t] - x) / 2;
	x += y;
	ll min_t = numeric_limits<ll>::max();
	int count = 0;
        for (int i = 0; i < k; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		ll t = a * x + b * y;
		if (t == min_t)
			count++;
                else if (t < min_t) {
			min_t = t;
			count = 1;
		}
	}
	printf("%lld %d\n", min_t, count);
	return 0;
}