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
125
126
127
128
129
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
ordered_set;	

struct splitmix64_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
 
	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};
 
template <typename K, typename V, typename Hash = splitmix64_hash>
using hash_map = __gnu_pbds::gp_hash_table<K, V, Hash>;
 
template <typename K, typename Hash = splitmix64_hash>
using hash_set = hash_map<K, __gnu_pbds::null_type, Hash>;

#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<pii, int> para;
const ll inf = 1e18 + 7;
const ll maxN = 2e3 + 5;
const ll MOD = 1e9 + 7;

ll n, m, k;
string s[maxN];
bool visited[maxN][maxN];
int dist[maxN][maxN];

bool inRange(int x, int y) {
	return x >= 0 && y >= 0 && x < n && y < m;
}

void BFS() {
	deque<pii> Q;
	Q.push_back({0, 0});
	dist[0][0] = 0;
	while (!Q.empty()) {
		pii p = Q.front(); Q.pop_front();
		int x = p.st, y = p.nd;
		if (visited[x][y]) continue;
		visited[x][y] = true;
		// cout << x << " " << y << " " << dist[x][y] << endl;
		FOR(i, -1, 1) {
			FOR(j, -1, 1) {
				if (abs(i) + abs(j) == 2) continue;
				int xx = x + i, yy = y + j;
				if (inRange(xx, yy) && !visited[xx][yy] && s[xx][yy] == '.') {
					if (i == -1 || j == -1) {
						if (dist[xx][yy] > dist[x][y] + 1) {
							dist[xx][yy] = dist[x][y] + 1;
							Q.push_back({xx, yy});
						}
					} else {
						if (dist[xx][yy] > dist[x][y]) {
							dist[xx][yy] = dist[x][y];
							Q.push_front({xx, yy});
						}
					}
				}
			}
		}
	}
}

// sprawdz MODULO!
int main() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	REP(i, n) {
		cin >> s[i];
	}
	REP(i, n) {
		REP(j, m) {
			dist[i][j] = MOD;
		}
	}
	BFS();
	if (dist[n - 1][m - 1] == MOD) {
		cout << -1 << endl;
		return 0;
	}
	ll ans = inf;
	int ile = 0;
	REP(_, k) {
		ll a, b;
		cin >> a >> b;
		ll d = dist[n - 1][m - 1];
		ll tmp = (n - 1 + m - 1 + d) * a + d * b;
		if (ans >= tmp) {
			if (ans == tmp) ile++;
			else {
				ile = 1;
				ans = tmp;
			}
		}
	}
	cout << ans << " " << ile << endl;
	return 0;
}