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
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 2000 + 10;
const ll INF = 1e18;
int n,m,k;
char t[nax][nax];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int d[nax][nax];

void bfs() {
	queue<pi>Q;
	queue<pi>Q2;
	Q.push({1,1});
	d[1][1] = 0;
	while(!Q.empty()||!Q2.empty()) {
		if(Q.empty()) {
			swap(Q, Q2);
		}
		pi x = Q.front();
		Q.pop();
		for(int i = 0; i < 4; ++i) {
			int a = x.ST + dx[i];
			int b = x.ND + dy[i];
			if(a < 1 || a > n || b < 1 || b > m) continue;
			if(i < 2) {
				if(d[x.ST][x.ND]<d[a][b]&&t[a][b]=='.') {
					Q.push({a,b});
					d[a][b] = d[x.ST][x.ND];
				} 
			}
			else {
				if(d[x.ST][x.ND] + 1 < d[a][b] && t[a][b] == '.') {
					Q2.push({a,b});
					d[a][b] = d[x.ST][x.ND] + 1;
				}
			}
		}
	}
}
				

int main() {_
	cin >> n >> m >> k;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			cin >> t[i][j];
			d[i][j] = 1000*1000*1000;
		}
	}
	bfs();
	ll ans = INF;
	int cnt = 0;
	//~ cout << d[n][m] << "\n";
	while(k--) {
		int a, b;
		cin >> a >> b;
		ll cur = (ll)b * d[n][m] + (ll)(n+m-2+d[n][m]) * a;
		//~ cout << cur << "\n";
		if(cur < ans) {
			ans = cur;
			cnt = 1;
		} else if(cur == ans) cnt++;
	}
	cout << ans << " " << cnt;
}