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
#include<iostream>
#include<utility>
#include<queue>
using namespace std;

int main()
{
	long long n,m,k; cin >> n >> m >> k;
	bool odw[n+2][m+2];
	for(int i=0; i<n+2;i++) {odw[i][0] = false; odw[i][m+1] = false;}
	for(int i=0; i<m+2;i++) {odw[0][i] = false; odw[n+1][i] = false;}	
	

	
	for(int i=1; i<n+1;i++) for(int j=1; j<m+1;j++)
	{
		char y; cin >> y;
		if(y=='.') odw[i][j]=true;
		else odw[i][j]=false;
	}
	
	typedef pair<long long,long long> para;
	typedef pair<para,long long> ppara;
	queue<ppara> q;
	long ans = 0;
	odw[1][1] = false;
	q.push(make_pair(make_pair(1,1),0));
	
	while(q.size()>0)
	{
		ppara x = q.front();
		q.pop();
		long long xloc = x.first.first;
		long long yloc = x.first.second;
		long long valloc = x.second;
		odw[xloc][yloc] = false;
		
		if (xloc == n && yloc == m)
		{
			ans = valloc;
			break;
		}
		else
		{
			if(odw[xloc-1][yloc])		q.push(make_pair(make_pair(xloc-1,yloc),valloc+1));
			if(odw[xloc+1][yloc])		q.push(make_pair(make_pair(xloc+1,yloc),valloc+1));
			if(odw[xloc][yloc-1])		q.push(make_pair(make_pair(xloc,yloc-1),valloc+1));
			if(odw[xloc][yloc+1])		q.push(make_pair(make_pair(xloc,yloc+1),valloc+1));
		}
		
	}
	
	long long ile = 1;
	long long mini = 9000000000;
	long long b = (ans-(n+m-2))/2;
	long long a = ans - b;
	
	for(int i=0; i<k; i++)
	{
		long long c,d;
		cin >> c >> d;
		long long an = a*c+b*d;
		if(an<mini)
		{
			mini = an;
			ile = 1;
		}
		else if(an == mini) ile++;
	}
	
	cout << mini << " " << ile <<endl;
	

	
	return 0;
}