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
 96
 97
 98
 99
100
101
#include "bits/stdc++.h" // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, m, k;
	cin >> n >> m >> k;
	vector<string> in(n);
	for(string &s : in)
		cin >> s;

	constexpr int sides = 4;
	const array<int, sides> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
	auto valid = [&](int x, int y) {
		return 0 <= x and x < n and 0 <= y and y < m;
	};

	const int inf = n * m;
	vector dist(n, vector<int>(m, inf));
	dist[0][0] = 0;
	deque<pair<int, int>> que = {{0, 0}};
	vector in_queue(n, vector<bool>(m));
	in_queue[0][0] = true;
	while(size(que)) {
		auto [x, y] = que.front();
		que.pop_front();
		in_queue[0][0] = false;

		REP(s, sides) {
			int xx = x + dx[s],
				yy = y + dy[s];
			if(valid(xx, yy) and in[xx][yy] == '.') {
				int weight = (xx < x or yy < y ? 1 : 0);
				if(dist[xx][yy] > dist[x][y] + weight) {
					dist[xx][yy] = dist[x][y] + weight;	
					if(weight == 0 and not in_queue[xx][yy]) {
						in_queue[xx][yy] = true;
						que.emplace_front(xx, yy);
					}
					else {
						in_queue[xx][yy] = true;
						que.emplace_back(xx, yy);
					}
				}
			}
		}
	}
	int d = dist[n - 1][m - 1];
	assert(d != inf);
	debug(d);

	LL ans_len = LL(1e18);
	int ans_cnt = 0;

	while(k --> 0) {
		int a, b;
		cin >> a >> b;
		LL len = a * LL(n + m - 2 + d) + b * LL(d);
		debug(a, b, len);
		if(len < ans_len) {
			ans_len = len;
			ans_cnt = 1;
		}
		else if(len == ans_len)
			++ans_cnt;
	}
	cout << ans_len << ' ' << ans_cnt << '\n';
}