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>
#define qio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x) cerr<<#x<<" "<<x<<endl
#define ll long long 
#define st first
#define nd second
using namespace std;

ll n, t, tab[2005][2005], done[2005][2005], w, x, y, dis[2005][2005], k, a, b, temp, minn = LLONG_MAX, ile, odl, m;
char ch;
string s;
priority_queue <pair<ll, pair<ll, ll>>> PQ;
int main()
{
	qio;
	cin >> n >> m >> k;

	for (int i = 0; i <= n + 1; i++) {
		if (i != 0 && i != n + 1)cin >> s;
		for (int j = 0; j <= m + 1; j++) {
			if (i == 0 || j == 0 || j == m + 1 || i == n + 1) tab[i][j] = 1;
			else {
				ch = s[j - 1];
				if (ch == 'X') tab[i][j] = 1;
			}
		}
	}

	PQ.push({ 0,{1,1} });
	while (!PQ.empty()) {
		w = -PQ.top().st;
		x = PQ.top().nd.st;
		y = PQ.top().nd.nd;
		PQ.pop();
		if (done[x][y] == 0) {
			done[x][y] = 1;
			dis[x][y] = w;
			if (tab[x + 1][y] != 1 && done[x + 1][y] == 0) PQ.push({ -w,{x + 1,y} });
			if (tab[x][y + 1] != 1 && done[x][y + 1] == 0) PQ.push({ -w,{x,y + 1} });
			if (tab[x - 1][y] != 1 && done[x - 1][y] == 0) PQ.push({ -w - 1,{x - 1,y} });
			if (tab[x][y - 1] != 1 && done[x][y - 1] == 0) PQ.push({ -w - 1,{x,y - 1} });
		}
	}
	odl = dis[n][m];
	for (int i = 1; i <= k; i++) {
		cin >> a >> b;
		temp = b * odl + a * (n + m - 2 + odl);

		if (temp == minn) {
			ile++;
		}
		else if (temp < minn) {
			minn = temp;
			ile = 1;
		}
	}

	cout << minn << " " << ile;




}