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
116
117
118
119
120
121
122
123
124
#include <iostream>
#include <vector>
#include <queue>
#include <cstdint>
#include <cstdio>
#include <cinttypes>

using namespace std;

vector<vector<bool>> map;

void readMap(int rows, int cols) {
	for (int i = 0; i < rows; ++i) {
		for (int j = 0; j < cols; ++j) {
			char point;
			cin >> point;
			if (point == 'X') {
				map[i][j] = false;
			}
		}
	}
}

inline bool isValid(int i, int j) {
	return (i >= 0 && j >= 0 && i < map.size() && j < map[0].size() && map[i][j]);
}

pair<int, int> calcFastestRoute() {
	vector<vector<pair<int, int>>> times(map.size(), vector<pair<int, int>>(map[0].size(), pair<int, int>(-1,-1)));
	times[0][0] = pair<int, int>(0,0);
	map[0][0] = false;
	queue<pair<int, int>> nodes;
	nodes.push(pair<int, int>(0,0));

	while(!nodes.empty()) {
		pair<int, int> node = nodes.front();
		nodes.pop();

		int i = node.first;
		int j = node.second;
		//up
		if (isValid(i-1, j)) {
			times[i-1][j] = times[i][j];
			times[i-1][j].second += 1;
			map[i-1][j] = false;
			nodes.push(pair<int, int>(i-1, j));
		}

		//right
		if (isValid(i, j+1)) {
			times[i][j+1] = times[i][j];
			times[i][j+1].first += 1;
			map[i][j+1] = false;
			nodes.push(pair<int, int>(i, j+1));
		}

		//down
		if (isValid(i + 1, j)) {
			times[i+1][j] = times[i][j];
			times[i+1][j].first += 1;
			map[i+1][j] = false;
			nodes.push(pair<int, int>(i+1, j));
		}

		//left
		if (isValid(i, j-1)) {
			times[i][j-1] = times[i][j];
			times[i][j-1].second += 1;
			map[i][j-1] = false;
			nodes.push(pair<int, int>(i, j-1));
		}

	}

	return times[map.size()-1][map[0].size()-1];
}

pair<uint64_t, int> findWinnerTime(pair<int, int> upsAndDowns, int friendsCount) {
	int up = upsAndDowns.first;
	int down = upsAndDowns.second;

	// cout << "up: " << up << ", down:"
	uint64_t myMin = 0;
	int count = 0;
	int minUp = 0;
	int minDown = 0;

	for (int i = 0; i < friendsCount; ++i) {
		int a, b;
		cin >> a >> b;
		// cout << "a: " << a << ", b: " << b << endl;
		if (minUp != 0 && a > minUp && b > minDown) {
			continue;
		}
		uint64_t totalTime = (uint64_t) a * (uint64_t) up + (uint64_t) b * (uint64_t) down;
		// cout << "total " << totalTime << endl;
		if (totalTime < myMin || myMin == 0) {
			minUp = a;
			minDown = b;
			myMin = totalTime;
			count = 1;
			// cout << i << " is min" << endl;
		} else if (totalTime == myMin) {
			count++;
		}
	}
	// cout << "cheapest is " << myMin << endl; 
	return pair<uint64_t, int> (myMin, count);
}

int main() {
	int rows, cols, friendsCount;
	cin >> rows >> cols >> friendsCount;

	map.resize(rows, vector<bool>(cols, true));
	readMap(rows, cols);

	pair<int, int> fastestRoute = calcFastestRoute();
	// cout << fastestRoute.first << " " << fastestRoute.second << endl; 
	pair<uint64_t, int> result = findWinnerTime(fastestRoute, friendsCount);

	cout << result.first << " " << result.second << endl;
	return 0;
}