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
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#ifdef LOC
#include "debuglib.h"
#else
#define deb(...)
#define DBP(...)
#endif
using namespace std;
using   ll         = long long;
using   Vi         = vector<int>;
using   Pii        = pair<int, int>;
#define pb           push_back
#define mp           make_pair
#define x            first
#define y            second
#define rep(i, b, e) for (int i = (b); i < (e); i++)
#define each(a, x)   for (auto& a : (x))
#define all(x)       (x).begin(), (x).end()
#define sz(x)        int((x).size())

char M[2048][2048];
int dist[2048][2048];

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cout << fixed << setprecision(10);

	int n, m, k;
	cin >> n >> m >> k;
	rep(i, 0, n) cin >> M[i];

	rep(i, 0, n) {
		rep(j, 0, m) {
			dist[i][j] = 1e9;
		}
	}

	queue<Pii> que;
	dist[0][0] = 0;
	que.push({0, 0});

	auto relax = [&](int i, int j, int d) {
		if (i >= 0 && j >= 0 && i < n && j < m && d < dist[i][j] && M[i][j] == '.') {
			dist[i][j] = d;
			que.push({i, j});
		}
	};

	while (!que.empty()) {
		Pii p = que.front();
		que.pop();
		relax(p.x-1, p.y, dist[p.x][p.y]+1);
		relax(p.x+1, p.y, dist[p.x][p.y]+1);
		relax(p.x, p.y-1, dist[p.x][p.y]+1);
		relax(p.x, p.y+1, dist[p.x][p.y]+1);
	}

	ll down = (dist[n-1][m-1] - (n+m-2)) / 2;
	ll up = n+m-2 + down;
	ll best = INT64_MAX, cnt = 0;

	while (k--) {
		ll a, b; cin >> a >> b;
		ll score = up*a + down*b;
		if (score < best) {
			best = score;
			cnt = 1;
		} else if (score == best) {
			cnt++;
		}
	}

	cout << best << ' ' << cnt << '\n';
	return 0;
}