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 thicc(boi) boi.size()
#define magiczne ios_base::sync_with_stdio(0);
#define linijki cin.tie(NULL);
#define f first
#define s second

using namespace std;

typedef pair <long long int, long long int> pii;

long long int cf[2007][2007];
vector <pii> xd[2007][2007];
pii lol[1000007];
bool visit[2007][2007];
queue <pii> q;
long long int depth[2007][2007];

void BFS(pii v)
{
	visit[v.f][v.s] = true;
	for (auto x : xd[v.f][v.s])
		if (!visit[x.f][x.s])
		{
			depth[x.f][x.s] = depth[v.f][v.s] + 1;
			q.push(x);
		}
}

int main()
{
    magiczne linijki;
    long long int n, m, k;
    char oof;
    cin >> n >> m >> k;
    for (int i = 0;i<n;i++)
	{
    	for (int j = 0;j<m;j++)
		{
			cin >> oof;
			cf[i][j] = (oof == '.' ? 1 : 0);
			if (!cf[i][j]) continue;
			if (i > 0)
				if (cf[i - 1][j] == 1)
				{
					xd[i][j].emplace_back(i - 1, j);
					xd[i - 1][j].emplace_back(i, j);
				}
			if (j > 0)
				if (cf[i][j - 1] == 1)
				{
					xd[i][j].emplace_back(i, j - 1);
					xd[i][j - 1].emplace_back(i, j);
				}
		}
	}
    for (int i = 0;i<k;i++)
    	cin >> lol[i].f >> lol[i].s;
	q.emplace(0, 0);
	while (thicc(q))
	{
		BFS(q.front());
		q.pop();
	}
	long long int res = LLONG_MAX, c, res2 = 1;
	for (int i = 0;i<k;i++)
	{
		c = (depth[n - 1][m - 1] - (n + m - 2))/2 * (lol[i].f + lol[i].s) + lol[i].f * (n + m - 2);
		if (res == c)
			res2++;
		else if (res > c)
		{
			res2 = 1;
			res = c;
		}
	}
	cout << res << ' ' << res2 << '\n';
	return 0;
}