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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <iostream>
using namespace std;


int main() 
{
	int n,m,k;
	char s[2020][2020];
	int t[2020][2020];

	int kol[4000400][2], pk=0, kk=0;
	
	int i,j;
	int x,y;

	cin >> n >> m >> k;
	//scanf("%d %d %d", &n, &m, &k);
	for (i=0; i<n; i++)	cin >> s[i];//scanf("%s",s[i]);

//	printf("%d %d %d\n", n, m, k);
//	for (i=0; i<n; i++)	scanf("%s\n",s[i]);
	
	for (i=0; i<n; i++)	
		  for (j=0; j<m; j++) t[i][j]=-1;
	
	kol[kk][0]=0;
	kol[kk][1]=0;
	kk++;
	t[0][0]=0;
	
	while (pk!=kk)
	{
		x=kol[pk][0];
		y=kol[pk][1];
		pk++;
		if (x==n-1 && y==m-1) break;
		if (x+1<n && t[x+1][y]==-1 && s[x+1][y]=='.')
		{
			kol[kk][0]=x+1;
			kol[kk][1]=y;
			kk++;
			t[x+1][y]=t[x][y]+1;
		}
		if (x-1>=0 && t[x-1][y]==-1 && s[x-1][y]=='.')
		{
			kol[kk][0]=x-1;
			kol[kk][1]=y;
			kk++;
			t[x-1][y]=t[x][y]+1;
		}
		if (y+1<m && t[x][y+1]==-1 && s[x][y+1]=='.')
		{
			kol[kk][0]=x;
			kol[kk][1]=y+1;
			kk++;
			t[x][y+1]=t[x][y]+1;
		}
		if (y-1>=0 && t[x][y-1]==-1 && s[x][y-1]=='.')
		{
			kol[kk][0]=x;
			kol[kk][1]=y-1;
			kk++;
			t[x][y-1]=t[x][y]+1;
		}
		
	}
//		for (i=0; i<n; i++)	
//		{
//		  for (j=0; j<m; j++) printf("%d\t",t[i][j]);
//		  printf("\n");
//		}
	
	long long wynik = t[n-1][m-1];
	long long wynik_d = (wynik-(n+m-2))/2;
	long long wynik_g = m + n -2 + (wynik-(n+m-2))/2;
//	printf("%d %d\n", wynik_d, wynik_g);	
		
	long long min = 4000000000000000;
	// printf("%lld\n", min);
	int ile = 0;
	long long g,d;
	for (int i=0; i<k; i++)
	{
		cin >> g >> d;
		//scanf("%d %d", &g,&d);
		wynik = wynik_g * g + wynik_d * d;
		if (wynik < min)
		{
			min = wynik;
			ile = 1;
		} else 
		if (wynik == min) ile++;
	}
	
	cout << min << " " << ile;
	
	//printf("%d %d", min, ile);
	
	// your code goes here
	return 0;
}