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
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define REPD(i,a,b) for (int i = (a); i >= (b); --i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define SZ(x) int((x).size())
#define DBG(v) cerr << #v << " = " << (v) << endl;
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define fi first
#define se second

const int N = 2020;
const int inf = (N+5)*(N+5)+3;

int dx[4] = {1, 0,-1, 0};
int dy[4] = {0, 1, 0,-1};

int n,m,k;
char s[N][N];
int d[N][N];

int main() {
	scanf("%d%d%d", &n, &m, &k);
	FORI(i,n) scanf("%s", s[i]+1);
	FOR(i,n+2) s[i][0] = s[i][m+1] = 'X';
	FOR(j,m+2) s[0][j] = s[n+1][j] = 'X';
	FORI(i,n+2) FORI(j,m+2) d[i][j] = inf;
	queue<int> q;
	q.push(1);
	q.push(1);
	d[1][1] = 0;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		int y = q.front(); q.pop();
		FOR(w,4) {
			int nx = x+dx[w], ny = y+dy[w];
			if (s[nx][ny] == 'X') continue;
			if (d[nx][ny] < inf) continue;
			d[nx][ny] = d[x][y] + 1;
			q.push(nx);
			q.push(ny);
		}
	}
	int L = d[n][m];
	int u = (L+2-n-m) / 2;
	int La = n+m-2 + u, Lb = u;
	//cerr << L << " " << u << " " << La << " " << Lb << "\n";
	ll best = 1000100100LL * inf;
	int cntbest = 0;
	FOR(i,k) {
		int a,b;
		scanf("%d%d", &a, &b);
		ll cur = 1LL * a * La + 1LL * b * Lb;
		if (cur < best) {
			best = cur;
			cntbest = 0;
		}
		if (cur == best) cntbest++;
	}
	printf("%lld %d\n", best, cntbest);
	return 0;
}