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
90
91
92
93
94
95
#include <iostream>
#include <string>
#include <set>
using namespace std;

#define N 2000
#define BIG 1'000'000'000LL

int n, m, k;

string tab[N];
set <pair<int, int>> best[N][N];

void add_to_best(int y, int x, int ups, int downs) {
	bool simpler = false;
	auto cp = best[y][x];
	for(auto el: best[y][x]) {
		// if(el.first < ups && el.second > downs) {
		// 	cp.insert({ups, downs});
		// } else if(el.first > ups && el.second < downs) {
		// 	cp.insert({ups, downs});
		// } else 
		if(el.first >= ups && el.second > downs) {
			cp.erase(el);
			cp.insert({ups, downs});
			simpler = true;
		} else if(el.first > ups && el.second >= downs) {
			cp.erase(el);
			cp.insert({ups, downs});
			simpler = true;
		} else if(el.first < ups && el.second <= downs) {
			simpler = true;
		} else if(el.first <= ups && el.second < downs) {
			simpler = true;
		}
	}
	if(!simpler) {
		cp.insert({ups, downs});
	}
	best[y][x] = cp;
}

void dfs(int y, int x, int ups, int downs) {
	int size_of_set = best[y][x].size();
	// cout << "For (" << y << ", " << x << ").size() == " << size_of_set << " -- before adding" << endl;
	add_to_best(y, x, ups, downs);
	// cout << "For (" << y << ", " << x << ").size() == " << best[y][x].size() << " -- after adding" << endl;
	if(size_of_set != best[y][x].size()) {
		if(y-1>=0 && tab[y-1][x] != 'X') {
			dfs(y-1, x, ups+1, downs);
		}
		if(x-1>=0 && tab[y][x-1] != 'X') {
			dfs(y, x-1, ups+1, downs);
		}
		if(y+1<n && tab[y+1][x] != 'X') {
			dfs(y+1, x, ups, downs+1);
		}
		if(x+1<m && tab[y][x+1] != 'X') {
			dfs(y, x+1, ups, downs+1);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> m >> k;
	for(int i = 0; i < n; ++i) {
		cin >> tab[i];
	}
	
	dfs(n-1, m-1, 0, 0);
	
	// cout << best[0][0].size() << endl;
	
	long long rec = best[0][0].begin()->first * BIG + best[0][0].begin()->second * BIG;
	int cnt = 0;
	for(int i = 0; i < k; ++i) {
		int a, b;
		cin >> a >> b;
		for(auto el: best[0][0]) {
			// cout << el.first << ", " << el.second << endl;
			long long act = a * el.first + b * el.second;
			if(act < rec) {
				rec = act;
				cnt = 1;
			} else if(act == rec) {
				++cnt;
			}
		}
	}
	
	cout << rec << " " << cnt << endl;
	
	return 0;
}