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


bool mapa[2005][2005];
int dp[2005][2005];
bool odw[2005][2005];

int x[4] = {1,-1,0,0};
int y[4] = {0,0,1,-1};

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= m; ++j){
			char c;
			cin >> c;
			mapa[i][j] = (c == '.' ? true : false);
		}
	}
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			dp[i][j] = 1e9;
	dp[1][1] = 0;

	queue <pair<pair<int,int>,int>> Q;
	Q.push({{1,1},-1});

	while (! Q.empty()){
		int i = Q.front().first.first;
		int j = Q.front().first.second;
		int d = Q.front().second;
		Q.pop();
		//cout << "(" << i << ", " << j << ")\n"; 
		if (odw[i][j])
			continue;
		dp[i][j] = d+1;
		odw[i][j] = true;
		for (int h = 0; h <= 3; ++h){
			int ii = i+y[h];
			int jj = j+x[h];
			if (min(ii,jj) < 1 || ii > n || jj > m || odw[ii][jj] || !mapa[ii][jj])
				continue;
			Q.push({{ii,jj},dp[i][j]});
		}
	}
	long long downs = (dp[n][m]-n-m+2)/2;
	long long ups = n+m-2+downs;

	long long mint = 1e18;
	int cnt = 0;

	for (int i = 1; i <= k; ++i){
		int a, b;
		cin >> a >> b;
		long long res = ups*a + downs*b;
		if (res < mint){
			mint = res;
			cnt = 0;
		}
		if (res == mint)
			cnt++;
	}

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