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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const long long INF = 100000000000000000LL;

vector<int> bfs_odl(vector<vector<int>>& g, int p) {
	queue<int> q;
	vector<int> odl(g.size(), -1);
	odl[p] = 0;
	q.push(p);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int v: g[x])
			if (odl[v] == -1) {
				odl[v] = odl[x] + 1;
				q.push(v);
			}
	}
	return odl;
}

int main() {
	ios_base::sync_with_stdio(0);
	int i, j, n, m, k, l;
	cin >> n >> m >> k;
	vector<string> plansza(n);
	vector<long long> a(k), b(k);
	for (i = 0; i < n; ++i)
		cin >> plansza[i];
	for (i = 0; i < k; ++i) 
		cin >> a[i] >> b[i];
	vector<vector<int>> g(n * m);
	auto dir = vector<vector<int>> {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	for (i = 0; i < n; ++i) 
		for (j = 0; j < m; ++j) 
			for (l = 0; l < 4; ++l) { 
				int x = i + dir[l][0];
				int y = j + dir[l][1];
				if (x >= 0 && y >= 0 && x < n && y < m && plansza[i][j] == '.' && plansza[x][y] == '.')
					g[j * n + i].push_back(y * n + x);
			}
	auto odl = bfs_odl(g, 0);
	int min_odl = odl[n * m - 1];
	long long z_gory = (min_odl - n - m + 2) / 2;
	long long wynik = INF;
	int ilu = 0;
	for (i = 0; i < k; ++i) {
		long long czas = z_gory * b[i] + (n + m - 2 + z_gory) * a[i];
		if (czas < wynik) {
			wynik = czas;
			ilu = 1;
		} else if (czas == wynik)
			ilu++;
	}
	cout << wynik << " " << ilu;
	return 0;
}