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

using namespace std;
using namespace __gnu_pbds;

constexpr int M=2e3+7;
constexpr int oo=1e9+7;
constexpr long long ooll=1e18+7;

bool blocked[M][M];
bool o[M][M];
int dist[M][M];
pair<int,int>r[4]={{1,0}, {-1,0}, {0,1}, {0,-1}};
queue<pair<int,int> >Q;
int n, m;

void bfs(int x, int y){
	int x2, x3, y2, y3;

	Q.push({x,y});
	
	while(Q.size()){
		x2 = Q.front().first;
		y2 = Q.front().second;
		Q.pop();
	
		if(o[x2][y2]) continue;
		o[x2][y2]=1;
	
		for(int i=0; i<4; i++){
			x3 = x2 + r[i].first;
			y3 = y2 + r[i].second;
			if(x3<0 || x3>=n || y2<0 || y3>=m || blocked[x3][y3]) continue;
			
			if(dist[x2][y2]+1 < dist[x3][y3]){
				dist[x3][y3] = dist[x2][y2]+1;
				Q.push({x3,y3});
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	string s;
	int k, howmany=0;
	long long a, b, x, best=ooll, cur;
	
	cin >> n >> m >> k;
	
	for(int i=0; i<n; i++){
		cin >> s;
		for(int j=0; j<m; j++) blocked[i][j] = (s[j]=='X');
	}
	
	for(int i=0; i<n; i++) for(int j=0; j<m; j++) dist[i][j] = oo * (i || j);
	
	bfs(0,0);
	
	x = dist[n-1][m-1] - (n+m-2);
	x>>=1;
	
	while(k--){
		cin >> a >> b;
		
		cur = a*(n+m-2 + x) + b*x; 
		
		if(cur < best){
			best = cur;
			howmany=1;
		}
		else if(cur==best) howmany++;
	}
	
	cout << best << ' ' << howmany;
	
	return 0;
}