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
83
84
85
86
87
88
#include <bits/stdc++.h>
 
#define st first
#define nd second
#define pb push_back
#define BOOST ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
#define PI 3.14159265359
 
using namespace std;
 
typedef long long ll;
constexpr ll MOD = 1000000007, hot = 29;
constexpr ll FOX = 1234567891, cute = 1007;
constexpr ll MEGAN = 1000000009, liv = 107;
constexpr int MXN = 2000+7 + 10, CZAPA = (1<<20), INF = 1000000000;

int n, m, k;
char grid[MXN][MXN];
int dp[MXN][MXN], guide[MXN][MXN];
int X[] = {1, -1, 0, 0};
int Y[] = {0, 0, 1, -1};
priority_queue<pair<int, pair<int, int> > > PQ;
ll result[1000007];

void dij(pair<int, int> start){
	dp[start.st][start.nd] = 0;
	PQ.push({0, start});
	while(!PQ.empty()){
		pair<int, int> v = PQ.top().nd;
		int dist = -PQ.top().st;
		PQ.pop();
		if(dp[v.st][v.nd] < dist){
			continue;
		}
		for(int i=0; i<4; i++){
			pair<int, int> u = {v.st + X[i], v.nd + Y[i]};
			if(grid[u.st][u.nd] == '.'){
				if(dp[u.st][u.nd] > dp[v.st][v.nd] + 1){
					dp[u.st][u.nd] = dp[v.st][v.nd] + 1;
					PQ.push({-dp[u.st][u.nd], u});
				}
			}
		}
	}
}

int main(){	
	BOOST;	

	cin>> n >> m >> k;
	for(int i=1; i<=n; i++){
		string s;
		cin>> s;
		for(int j=1; j<=m; j++){
			grid[i][j] = s[j-1];
			dp[i][j] = INF;
		}
	}
	for(int i=0; i<=n+1; i++){
		grid[i][0] = 'X';
		grid[i][m+1] = 'X';
	}
	for(int i=0; i<=m+1; i++){
		grid[0][i] = 'X';
		grid[n+1][i] = 'X';
	}
	dij({1, 1});
	ll up = n-1 + m - 1, down = 0;
	ll rest = dp[n][m] - n - m + 2;
	up += rest / 2;
	down += rest / 2;
	ll ans = 1000000000000000000;
	int counter = 0;
	for(int i=0; i<k; i++){
		ll a, b;
		cin>> a >> b;
		result[i] = up * a + down * b;
		ans = min(ans, result[i]);
	}
	for(int i=0; i<k; i++){
		if(ans == result[i])
			counter++;
	}
	cout<< ans << ' ' << counter << '\n';
	
	
	return 0;
}