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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/*
 * author: pavveu
 * task: Potyczki Algorytmiczne 2020 Runda 4 - Wycieczka Gorska [C]
*/

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;

#define FOR(iter, val) for(int iter = 0; iter < (val); iter++)
#define all(x) begin(x), end(x)

template<typename T>
void initialize_matrix(vector<vector<T>>& matrix, int rows, int cols, T val) {
	assert(matrix.empty());
	FOR(row, rows) 
		matrix.emplace_back(cols, val);
}

struct pos {
	int r, c;
	pos(int rr, int cc) : r{rr}, c{cc} {}
};

pos operator+(pos a, pos b) {
	return { a.r + b.r, a.c + b.c };
}

struct bfs_engine {
	vector<string> grid;
	unsigned rows, cols;

	bfs_engine(vector<string>& g) : grid(g), rows(g.size()), cols(g[0].size()) {}

	pair<int, int> search(pos start, pos goal) {
		const int inf = 1e9;

		// bot, right, top, left
		array<pos, 4> dirs {{ {1, 0}, {0, 1}, {-1, 0}, {0, -1} }};

		vector<vector<pair<int,int>>> dist;
		initialize_matrix(dist, rows, cols, {inf, inf});

		dist[start.r][start.c] = {0, 0};
		queue<pos> q;
		q.push(start);

		while ( q.size() ) {
			pos u { q.front() };
			q.pop();

			int i { 0 };
			for (pos d : dirs) {
				pos v { u + d };
				if ( (unsigned) v.r < rows && (unsigned) v.c < cols ) {
					if( grid[v.r][v.c] != 'X' && dist[v.r][v.c].first == inf ) {
						dist[v.r][v.c] = dist[u.r][u.c];
						// is a-type direction
						if ( i < 2 ) dist[v.r][v.c].first++;
						// is b-type direction
						else dist[v.r][v.c].second++;
						q.push(v);
					}
				}
				i++;
			}
		}

		return dist[goal.r][goal.c];
	}
};

void go() {
	int rows, cols, n; 
	cin >> rows >> cols >> n;

	vector<string> grid(rows);
	for (auto& row : grid) cin >> row;
	
	bfs_engine bfs(grid);

	auto[cost_a, cost_b] = bfs.search({0, 0}, {rows - 1, cols - 1});

	const ll inf = 1e9 + 10;

	ll min_time { inf * inf };
	int count { 0 };
	while ( n-- ) {
		ll a, b;
		cin >> a >> b;
		ll time { a * cost_a + b * cost_b };
		if ( time < min_time ) {
			min_time = time;
			count = 1;
		}
		else if ( time == min_time ) {
			count++;
		}
	}
	cout << min_time << " " << count << endl;
}

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

	go();
	// test(100);

	return 0;
}