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
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;

const int N = 2e3 + 5;
const int M = 1e6 + 6;
const long long INF = 1e18 + 5;

bool tab[N][N];
bool odw[N][N];
pair <long long, long long> odl[N][N];
long long g[M];
long long d[M];

int n, m, k;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++){
		string s;
		cin >> s;
		for(int j = 1; j <= m; j++){
			if(s[j - 1] == '.') tab[i][j] = 1;
			odl[i][j] = make_pair(INF, INF);
		}
	}
	
	for(int i = 1; i <= k; i++){
		long long a, b;
		cin >> a >> b;
		g[i] = a;
		d[i] = b;
	}
	
	odl[1][1] = make_pair(0, 0);
	priority_queue <pair <int, pair <int, int> > > q;
	q.push(make_pair(0, make_pair(1, 1)));
	while(!q.empty()){
		long long dis = -q.top().first;
		int x = q.top().second.first;
		int y = q.top().second.second;
		q.pop();
		
		if(odw[x][y]) continue;
		
		odw[x][y] = true;
		
		if(tab[x + 1][y] && dis + 1 < odl[x + 1][y].first + odl[x + 1][y].second){
			odl[x + 1][y].first = odl[x][y].first + 1;
			odl[x + 1][y].second = odl[x][y].second;
			q.push(make_pair(-dis - 1, make_pair(x + 1, y)));
		}
		
		if(tab[x - 1][y] && dis + 1 < odl[x - 1][y].first + odl[x - 1][y].second){
			odl[x - 1][y].first = odl[x][y].first;
			odl[x - 1][y].second = odl[x][y].second + 1;
			q.push(make_pair(-dis - 1, make_pair(x - 1, y)));
		}
		
		if(tab[x][y + 1] && dis + 1 < odl[x][y + 1].first + odl[x][y + 1].second){
			odl[x][y + 1].first = odl[x][y].first + 1;
			odl[x][y + 1].second = odl[x][y].second;
			q.push(make_pair(-dis - 1, make_pair(x, y + 1)));
		}
		
		if(tab[x][y - 1] && dis + 1 < odl[x][y - 1].first + odl[x][y - 1].second){
			odl[x][y - 1].first = odl[x][y].first;
			odl[x][y - 1].second = odl[x][y].second + 1;
			q.push(make_pair(-dis - 1, make_pair(x, y - 1)));
		}
	}
	
	long long gory = odl[n][m].first, doly = odl[n][m].second;
	long long minn = INF;
	int l = 0;
	
	for(int i = 1; i <= k; i++){
		if(g[i] * gory + d[i] * doly < minn){
			minn = g[i] * gory + d[i] * doly;
			l = 1;
		}
		else if(g[i] * gory + d[i] * doly == minn) l++;
	}
	
	cout << minn << " " << l;
	
	/*cout << "\n";
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cout << "(" << odl[i][j].first << "," << odl[i][j].second << ") ";
		}
		cout << "\n";
	}*/
}