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>
#define mp make_pair
#define pb push_back
#define INF 0x3f3f3f3f
using namespace std;
vector<int> g[4000009];
int n, m, k, licznik, wa, wb, ile;
long long mini=INF, wynik;
char c;
bool jaki[4000009];
int fun(int a, int b){
	vector<int> d(n*m+1, INF);
	d[1]=0;
	deque<int> q;
	q.push_front(1);
	while (!q.empty()) {
	    int v = q.front();
	    q.pop_front();
	    for (auto edge : g[v]) {
	        int u = edge, w;
	        if(u==v+1 || u==v+m)
	        	w=a;
	        else
	        	w=b;
	        if (d[v] + w < d[u]) {
	            d[u] = d[v] + w;
	            if (w == 1)
	                q.push_back(u);
	            else
	                q.push_front(u);
	        }
	    }
	}
	return d[n*m];
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m>>k;
	for(int i=1; i<=n*m; i++){
		cin>>c;
		if(c=='.')
			jaki[i]=1;
	}
	licznik=0;
	for(int j=1; j<=n; j++){
		for(int i=1; i<m; i++){
			if(jaki[licznik+i] && jaki[licznik+i+1]){
			g[licznik+i].pb(licznik+i+1);
			g[licznik+i+1].pb(licznik+i);
		}
		}
		licznik+=m;
	}
	for(int j=1; j<=m; j++){
		licznik=j;
		for(int i=1; i<n; i++){
			if(jaki[licznik]&&jaki[licznik+m]){
			g[licznik].pb(licznik+m);
			g[licznik+m].pb(licznik);
		}
			licznik+=m;
		}
	}
	int dijb=fun(0, 1);
	int dija=fun(1, 0);
	for(int i=0; i<k; i++){
		cin>>wa>>wb;
		wynik=(long long)dija*wa+(long long)dijb*wb;
		if(wynik<mini){
			mini=wynik;
			ile=1;
		}
		else if(wynik==mini)
			ile++;
	}
	cout<<mini<<" "<<ile<<"\n";
	return 0;
}