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
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define pr(a, b) make_pair(a, b)
const int LIM=2e3+7;
const long long INF=1e18+7;
string T[LIM];
long long odl[LIM][LIM], a[LIM][LIM], b[LIM][LIM];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	rep(i, n) cin >> T[i];
	queue<pair<int,int> >q;
	q.push(pr(0, 0));
	rep(i, n) rep(j, m) odl[i][j]=INF;
	odl[0][0]=0;
	while(!q.empty()) {
		int x=q.front().first, y=q.front().second; q.pop();
		if(x<n-1 && odl[x+1][y]>odl[x][y]+1 && T[x+1][y]=='.') {
			odl[x+1][y]=odl[x][y]+1;
			a[x+1][y]=a[x][y]+1;
			b[x+1][y]=b[x][y];
			q.push(pr(x+1, y));
		}
		if(y<m-1 && odl[x][y+1]>odl[x][y]+1 && T[x][y+1]=='.') {
			odl[x][y+1]=odl[x][y]+1;
			a[x][y+1]=a[x][y]+1;
			b[x][y+1]=b[x][y];
			q.push(pr(x, y+1));
		}
		if(x>0 && odl[x-1][y]>odl[x][y]+1 && T[x-1][y]=='.') {
			odl[x-1][y]=odl[x][y]+1;
			a[x-1][y]=a[x][y];
			b[x-1][y]=b[x][y]+1;
			q.push(pr(x-1, y));
		}
		if(y>0 && odl[x][y-1]>odl[x][y]+1 && T[x][y-1]=='.') {
			odl[x][y-1]=odl[x][y]+1;
			a[x][y-1]=a[x][y];
			b[x][y-1]=b[x][y]+1;
			q.push(pr(x, y-1));
		}
	}
	long long ans=INF, l=1;
	while(k--) {
		long long x, y;
		cin >> x >> y;
		if(ans>a[n-1][m-1]*x+b[n-1][m-1]*y) {
			l=1;
			ans=a[n-1][m-1]*x+b[n-1][m-1]*y;
		} else if(ans==a[n-1][m-1]*x+b[n-1][m-1]*y) ++l;
	}
	cout << ans << " " << l;
}