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
#include <bits/stdc++.h>
using namespace std;
char tab[2002][2002];
priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > >pq;
bool odw[2001][2001];
int dol, n, m;
void dijkstra()
{
	while (!pq.empty())
	{
		int a=pq.top().first, b=pq.top().second.first, c=pq.top().second.second;
//		cout<<a<<" "<<b<<" "<<c<<endl;
		pq.pop();
		if (b==n && c==m)
		{
			dol=a;
			return;
		}
		if (odw[b][c])
			continue;
		odw[b][c]=true;
//		odl[b][c]=a;
		if (!odw[b+1][c] && tab[b+1][c]=='.')
			pq.push(make_pair(a, make_pair(b+1, c)));
		if (!odw[b][c+1] && tab[b][c+1]=='.')
			pq.push(make_pair(a, make_pair(b, c+1)));
		if (!odw[b-1][c] && tab[b-1][c]=='.')
			pq.push(make_pair(a+1, make_pair(b-1, c)));
		if (!odw[b][c-1] && tab[b][c-1]=='.')
			pq.push(make_pair(a+1, make_pair(b, c-1)));
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int k;
	cin>>n>>m>>k;
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
			cin>>tab[i][j];
	}
	pq.push(make_pair(0, make_pair(1, 1)));
	dijkstra();
//	cout<<dol<<endl;
	long long mn=LLONG_MAX, odp=0;
	for (int i=0; i<k; i++)
	{
		int a, b;	cin>>a>>b;
		long long pom=(long long)(n+m+dol-2)*(long long)a+(long long)b*(long long)dol;
//		cout<<"WYNIK "<<i<<" "<<pom<<endl;
		if (pom==mn)
			odp++;
		else if (pom<mn)
		{
			odp=1;
			mn=pom;
		}
	}
	cout<<mn<<" "<<odp;
	return 0;
}