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

using namespace std;

const int razy = 2020*2020;

int n, m, k;
char s[2010][2010];
vector <int> g[razy];
int odl[razy], odw[razy];
queue <pair <int, int> > q;
long long a[razy], b[razy], la, lb;

int konv(int i, int j)
{
	return m*i+j;
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for(int i=0; i<n; ++i)
	{
		scanf("%s", s[i]);
	}
	for(int i=0; i<n-1; ++i)
	{
		for(int j=0; j<m; ++j)
		{
			if(s[i][j]=='.'&&s[i+1][j]=='.')
			{
				g[konv(i, j)].push_back(konv(i+1, j));
				g[konv(i+1, j)].push_back(konv(i, j));
			}
		}
	}
	for(int i=0; i<n; ++i)
	{
		for(int j=0; j<m-1; ++j)
		{
			if(s[i][j]=='.'&&s[i][j+1]=='.')
			{
				g[konv(i, j)].push_back(konv(i, j+1));
				g[konv(i, j+1)].push_back(konv(i, j));
			}
		}
	}
	q.push({0, 0});
	while(!q.empty())
	{
		auto h=q.front();
		q.pop();
		if(odw[h.first])
		{
			continue;
		}
		odw[h.first]=1;
		odl[h.first]=h.second;
		for(auto xd : g[h.first])
		{
			q.push({xd, h.second+1});
		}
	}
	la=n+m-2+(odl[konv(n-1, m-1)]-(n+m-2))/2;
	lb=(odl[konv(n-1, m-1)]-(n+m-2))/2;
	long long mi=(1ll<<60);
	for(int i=0; i<k; ++i)
	{
		scanf("%lld%lld", &a[i], &b[i]);
		mi=min(mi, la*a[i]+lb*b[i]);
	}
	int licz=0;
	for(int i=0; i<k; ++i)
	{
		if(mi==la*a[i]+lb*b[i])
		{
			++licz;
		}
	}
	printf("%lld %d\n", mi, licz);
	return 0;
}