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

struct punkt{int x,y;
	punkt(int x,int y):x(x),y(y){};
	punkt(){};
};

int trasa(int n, int m, vector<string> &p) {
	queue<punkt> Q;
	vector<vector<int> > V(n);
	for (int i=0;i<n;i++) V[i].resize(m);
	Q.push(punkt(0,0));
	p[0][0]='#';
	while (!Q.empty()) {
		punkt P = Q.front(); Q.pop();
		if (P.x>0 && p[P.y][P.x-1]=='.') {
			p[P.y][P.x-1]='#';
			V[P.y][P.x-1]=V[P.y][P.x]+1;
			Q.push(punkt(P.x-1,P.y));
		}
		if (P.x<m-1 && p[P.y][P.x+1]=='.') {
			p[P.y][P.x+1]='#';
			V[P.y][P.x+1]=V[P.y][P.x]+1;
			Q.push(punkt(P.x+1,P.y));
		}
		if (P.y>0 && p[P.y-1][P.x]=='.') {
			p[P.y-1][P.x]='#';
			V[P.y-1][P.x]=V[P.y][P.x]+1;
			Q.push(punkt(P.x,P.y-1));
		}
		if (P.y<n-1 && p[P.y+1][P.x]=='.') {
			p[P.y+1][P.x]='#';
			V[P.y+1][P.x]=V[P.y][P.x]+1;
			Q.push(punkt(P.x,P.y+1));
		}
	}
	return V[n-1][m-1];
}	


int main() {
	ios_base::sync_with_stdio(0);
	int n,m,k;
	cin >> n >> m >> k;
	vector<string> plansza(n);
	for (int i=0;i<n;i++) cin >> plansza[i];
	int dt = trasa(n,m,plansza);
	//cout << dt << endl;
	vector<long long> czasy;
	for (int i=0;i<k;i++) {
		long long a,b;
		cin >> a >> b;
		long long czas = (dt-(n+m-2))*(a+b)/2+(n+m-2)*a;
		czasy.push_back(czas);
	}
	sort(czasy.begin(),czasy.end());
	int szybcy = 1;
	for(int i=1;i<k;i++) {
		if (czasy[i]==czasy[0])
			szybcy++;
		else
			break;
	}
	cout << czasy[0] << " " << szybcy;
	return 0;
}