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
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, int> PILL;
typedef pair<ll, ll> PLL;

const int MAX_N = 3e5+5;
const int M = 3e4+5;
const ll INF = (ll)(1e18);
const int inf = 2e9;
const ll MOD = 1000000007LL;

int n, m, k;
string grid[2005];
ll dist[2005][2005];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

bool ok(int r, int c) {
	if (r < 0 || r >= n || c < 0 || c >= m) return false;
	if (grid[r][c] == 'X') return false;
	return true;
}

// find minimum number of downhill moves
void bfs() {
	deque<PII> Q;
	Q.push_front({0, 0});
	
	while (!Q.empty()) {
		int r = Q.front().first;
		int c = Q.front().second;
		Q.pop_front();
		
		for (int i = 0; i < 4; i++) {
			int newR = r + dx[i];
			int newC = c + dy[i];
			if (!ok(newR, newC)) continue;
			ll cost = 0LL;
			if (dx[i] == -1 || dy[i] == -1) cost = 1LL;
			
			if (dist[r][c] + cost < dist[newR][newC]) {
				dist[newR][newC] = dist[r][c] + cost;
				if (cost == 0)
					Q.push_front({newR, newC});
				else 
					Q.push_back({newR, newC});
			}
		}
	}
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
		
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		cin >> grid[i];
		for (int j = 0; j < m; j++) {
			dist[i][j] = INF;
		}
	}
	dist[0][0] = 0LL;
	
	bfs();
	
	ll mini = INF;
	int cnt = 0;
	ll must = (ll)(n + m - 2);
	for (int i = 0; i < k; i++) {
		ll a, b;
		cin >> a >> b;
		ll tmp = a * must + dist[n-1][m-1] * (a + b);
		//cout << i << ": " << tmp << '\n';
		if (tmp < mini) {
			mini = tmp;
			cnt = 1;
		} else if (tmp == mini) cnt++;
	}
	
	cout << mini << ' ' << cnt << '\n';
	
    return 0;
}