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
#include <bits/stdc++.h>
#define PB push_back
using namespace std;
typedef unsigned long long int ll;
typedef vector <int> vi;
typedef pair <int,int> p_i;
#define FOR(k,a,b) for(int k=(a); k < (b); ++k)
#define fst first
#define snd second
const int N=1000001;
ll prt = (ll)1000000007;
int main()
{
	int n,m,k;
	scanf("%d %d %d\n",&n,&m,&k);
	vector <string> safety;
	for(int i=0;i<n;i++){
		string s;
		getline(cin,s);
		safety.PB(s);
	}
	vector <p_i> speed;
	for(int i=0;i<k;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		p_i p = make_pair(a,b);
		speed.PB(p);		
	}
	
	vector <vector<p_i>> steps;
	for(int i=0;i<n;i++){
		vector <p_i> v;
		for(int j=0;j<m;j++){
			p_i p = make_pair(-1,-1);
			v.PB(p);
		}
		steps.PB(v);
	}
	steps[0][0].fst = 0;
	steps[0][0].snd = 0;
	queue <p_i> Q;
	Q.push(p_i(0,0));
	int d_i[4] = {-1,0,1,0};
	int d_j[4] = {0,1,0,-1};
	
	while(!Q.empty()){
		p_i p = Q.front();
		Q.pop();
		int w = p.fst;
		int k = p.snd;
		for(int i=0;i<4;i++){
			if(w+d_i[i]>=0 && w+d_i[i]<n && k+d_j[i]>=0 && k+d_j[i]<m){
				if(safety[w+d_i[i]][k+d_j[i]]=='.'){
					if(steps[w+d_i[i]][k+d_j[i]].fst==-1){
						steps[w+d_i[i]][k+d_j[i]].fst = steps[w][k].fst;
						steps[w+d_i[i]][k+d_j[i]].snd = steps[w][k].snd;
						if(i==1 || i==2)steps[w+d_i[i]][k+d_j[i]].fst++;
						else steps[w+d_i[i]][k+d_j[i]].snd++;
						Q.push(p_i(w+d_i[i],k+d_j[i]));
					}
				}
			}
		}
	}
	
	ll fastest_time =ULLONG_MAX;
	for(int i=0;i<k;i++){
		ll time = (ll)speed[i].fst*(ll)steps[n-1][m-1].fst + (ll)speed[i].snd*(ll)steps[n-1][m-1].snd;
		fastest_time = min(fastest_time,time);
	}
	int res = 0;
	for(int i=0;i<k;i++){
		ll time = (ll)speed[i].fst*(ll)steps[n-1][m-1].fst + (ll)speed[i].snd*(ll)steps[n-1][m-1].snd;
		if(time==fastest_time)res++;
	}
	
	printf("%llu %d",fastest_time,res);
	return 0;
}