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
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <tuple>
#include <climits>

using namespace std;

using Prios = vector<vector<int>>;
using Coords = pair<int, int>;

struct Comp {
	Comp(const Prios &p) : _p{p} {}
	bool operator()(const Coords &lhs, const Coords &rhs) const {
		return make_tuple(_p[lhs.first][lhs.second], lhs.first, lhs.second) <
			make_tuple(_p[rhs.first][rhs.second], rhs.first, rhs.second);
	}
	const Prios &_p;
};

int main() {
	ios_base::sync_with_stdio(0);

	int N, M, K;

	cin >> N >> M >> K;

	vector<string> V(N, string());

	for (int i = 0; i < N; i++) {
		V[i].reserve(M+1);
		cin >> V[i];
	}

	Prios downs(N, vector<int>(M, INT_MAX));

	auto q = set<Coords,Comp>(Comp(downs));

	downs[0][0] = 0;
	q.insert(Coords(0,0));

	auto valid = [&N, &M](int x, int y) {
		return x>=0 && x<N && y >=0 && y<M;
	};

	auto safe = [&V](int x, int y) {
		return V[x][y]=='.';
	};

	auto check = [&valid, &safe, &q, &downs](int x, int y, int current) {
		if (!valid(x,y) || !safe(x,y))
			return;

		if (current < downs[x][y]) {
			q.erase(Coords(x,y));
			downs[x][y] = current;
			q.insert(Coords(x,y));
		}
	};

	while (!q.empty()) {
		auto c = *q.begin();
		q.erase(q.begin());
		int current = downs[c.first][c.second];

		check(c.first-1,c.second, current + 1);
		check(c.first+1,c.second, current);
		check(c.first,c.second-1, current + 1);
		check(c.first,c.second+1, current);
	}

	int d = downs[N-1][M-1];
	unsigned long long cnst = N-1 + M-1;

	unsigned long long min = ULLONG_MAX;
	int cnt = 0;
	for (int i = 0; i < K; i++) {
		unsigned long long a, b;
		cin >> a >> b;
		unsigned long long s = cnst*a + d*(a+b);
		if (s < min) {
			cnt = 0;
			min = s;
		}
		if (s == min)
			cnt++;
	}

	cout << min << " " << cnt << endl;

	return 0;
}