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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, m, t[2005][2005], dist[2005][2005], a, b, Q;
queue<pair<int, int>> q[2];
string s;
int32_t main() {
	ios_base::sync_with_stdio(0);
	cin >> n >> m >> Q;
	for(int i = 1; i <= n; i++) {
		cin >> s;
		for(int j = 1; j <= m; j++) {
			t[i][j] = (s[j - 1] == '.' ? 1 : 0);
			dist[i][j] = 1e9;
		}
	}

	int par = 0;
	dist[1][1] = 0;
	q[par].push({1, 1});
	while(!q[par].empty()) {
		while(!q[par].empty()) {
			int x = q[par].front().first, y = q[par].front().second;
			q[par].pop();
			if(dist[x][y] % 2 != par) continue;

			if(t[x + 1][y] && dist[x + 1][y] > dist[x][y]) {
				dist[x + 1][y] = dist[x][y];
				q[par].push({x + 1, y});
			}

			if(t[x][y + 1] && dist[x][y + 1] > dist[x][y]) {
				dist[x][y + 1] = dist[x][y];
				q[par].push({x, y + 1});
			}

			if(t[x - 1][y] && dist[x - 1][y] > dist[x][y] + 1) {
				dist[x - 1][y] = dist[x][y] + 1;
				q[!par].push({x - 1, y});
			}

			if(t[x][y - 1] && dist[x][y - 1] > dist[x][y] + 1) {
				dist[x][y - 1] = dist[x][y] + 1;
				q[!par].push({x, y - 1});
			}
		}

		par = !par;
	}

	ll ans = 1e18;
	int cnt = 0;	
	while(Q--) {
		cin >> a >> b;
		ll len = 1LL * (n + m - 2) * a + 1LL * dist[n][m] * (a + b);
		if(len == ans)
			cnt++;
		else if(len < ans) {
			ans = len;
			cnt = 1;
		}
	}

	cout << ans << " " << cnt << "\n";
}