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
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;

const int MAXN = 2000 + 7;
const int INF = 1000*1000*1000 + 7;

char t[MAXN][MAXN];
bool odw[MAXN][MAXN];
int odl[MAXN][MAXN];
int ile_r[MAXN][MAXN];

pair<int, int> R[4] = {
	{-1, 0},
	{0, -1},
	{0, 1},
	{1, 0}
};

int n, m;

void BFS(pair<int, int> start)
{
	queue<pair<pair<int, int>, int> > Q;
	Q.push({start, 0});
	odw[start.fi][start.se] = true;
	while(!Q.empty())
	{
		pair<int, int> v = Q.front().fi;
		int w = Q.front().se;
		ile_r[v.fi][v.se] = w;
		Q.pop();
		for(int i = 0; i < 4; i++)
		{
			pair<int, int> u = {v.fi+R[i].fi, v.se+R[i].se};
			if(odw[u.fi][u.se] || u.fi < 1 || u.fi > n || u.se < 1 || u.se > m || t[u.fi][u.se] == 'X')
				continue;
			odw[u.fi][u.se] = true;
			odl[u.fi][u.se] = odl[v.fi][v.se] + 1;
			Q.push({u, w+(R[i].fi > 0 || R[i].se > 0)});
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	int k;
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> t[i][j];

	BFS({1, 1});
	ll minn = (ll)INF*(ll)INF;
	int ile = 0;
	for(int i = 1; i <= k; i++)
	{
		ll a, b;
		cin >> a >> b;
		ll wyn = a*(ll)ile_r[n][m] + b*(ll)(odl[n][m] - ile_r[n][m]);
		if(wyn == minn)
			ile++;
		if(wyn < minn)
			minn = wyn, ile = 1;
	}
	cout << minn << ' ' << ile << '\n';
	return 0;
}