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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;

int n, m, k;
string t[2009];

queue<pair<int, int> >stos;
const pair<int, int> tab[4] = {make_pair(1, 0), make_pair(0, 1), make_pair(-1, 0), make_pair(0, -1)};

pair<int, int> odw[2009][2009];

bool check(pair<int, int> b){
	if(b.first >=0 && b.second >=0 && b.first <n && b.second <m && t[b.first][b.second] != 'X' && odw[b.first][b.second].first==0)
		return true;
	return false;
}

pair<int, int> operator + (const pair<int, int> & a, const pair<int, int> & b){
	return make_pair(a.first+b.first, a.second+b.second);
}


void bfs(){
	t[0][0]='X';
	stos.push(make_pair(0, 0));
	while(!stos.empty()){
		pair<int, int> tmp = stos.front();
		stos.pop();
		for(int x=0; x<4; x++){
			pair<int, int> next = tmp + tab[x];
			if(check(next)){
				if(x < 2){
					odw[next.first][next.second].first = odw[tmp.first][tmp.second].first + 1;
					odw[next.first][next.second].second = odw[tmp.first][tmp.second].second;
				}
				else{
					odw[next.first][next.second].first = odw[tmp.first][tmp.second].first;
					odw[next.first][next.second].second = odw[tmp.first][tmp.second].second + 1;
				}
				stos.push(next);
			}
		}
		
	}
}

int main(){
	ios::sync_with_stdio(0);
	
	cin>>n>>m>>k;
	for(int i=0; i<n; i++){
		cin>>t[i];
	}
	bfs();
	LL res=999999999999999999L;
	int ile=0;
	for(int i=0; i<k; i++){
		LL a, b, tmp;
		cin>>a>>b;
		tmp = a*odw[n-1][m-1].first + b*odw[n-1][m-1].second;
		if(tmp < res){
			res = tmp;
			ile = 1;
		}
		else if(tmp == res){
			ile++;
		}
	}
	cout<<res<<" "<<ile<<"\n";
	return 0;
}