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
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

#ifdef HOME_
    #define DEBUG(x) x
#else
    #define DEBUG(x)
#endif
#define REP(x,n) for(int x=0;x<(n);++x)
#define FOREACH(x,n) for(__typeof(n.begin()) x = (n).begin(); x != (n).end(); ++x)

using namespace std;
const int MAX_N = 2001;
const long long BILLION = 1000000000LL;

int n,m,k;
int a,b;
typedef pair<int,int> PII;

struct Info {
	long long distance;
	pair<int,int> prev;
	char iteration;
	Info(): distance(0x7FFFFFFFFFFFFFFFLL), iteration(0) {}
};

string vertex[MAX_N];
Info dist[MAX_N][MAX_N];
long long dist11, dist12, dist21, dist22;

struct compare {
	bool operator()(const PII& a, const PII& b) const {
		const Info& ia = dist[a.first][a.second];
		const Info& ib = dist[b.first][b.second];
		return ia.iteration != ib.iteration
			? ia.iteration < ib.iteration
			: ia.distance != ib.distance
				? ia.distance < ib.distance
				: a.first == b.first ? a.second<b.second : a.first<b.first;
	}
};

#define PROCESS(x,y,w)	DEBUG(cerr << "check " << (x)<<","<<(y)<<" - "<<((x>=0)&&(y>=0) ? vertex[x][y] : '/')<<endl;) \
												if ((x)>=0 && (y)>=0 && (x)<n && (y)<m && vertex[x][y]=='.') {\
													Info& i = dist[x][y];\
													if (i.iteration != cycle) {\
														i.iteration = cycle;\
														i.distance = topi.distance + w;\
														i.prev = top;\
														q.insert(make_pair(x,y));\
													} else if (i.distance > topi.distance+w) {\
														q.erase(make_pair(x,y));\
														i.distance = topi.distance + w;\
														i.prev = top;\
														q.insert(make_pair(x,y));\
													}\
												}

void processGraph(char cycle, long long w1, long long w2) {
	dist[0][0].iteration = cycle;
	dist[0][0].distance = 0LL;
	set<PII, compare> q;
	q.insert(make_pair(0,0));
	while(!q.empty()) {
		PII top = *q.begin();
		Info& topi = dist[top.first][top.second];
		q.erase(q.begin());
		DEBUG(
			cerr << "Procesing " << top.first<< "," << top.second << ", dist=" << topi.distance << endl;
		)
		if (top.first == n-1 && top.second == m-1)
				break; // reached end point
		PROCESS(top.first-1, top.second, w1);
		PROCESS(top.first, top.second-1, w1);
		PROCESS(top.first+1, top.second, w2);
		PROCESS(top.first, top.second+1, w2);
		DEBUG(
			cerr << "After processing: " <<endl;
			FOREACH(it, q)
				cerr << "("<<it->first<<","<<it->second<<"), ";
			cerr<<endl;
		)
	}
}

void processGraph() {
	processGraph(1, 1, BILLION);
	dist11 = dist[n-1][m-1].distance / BILLION;
	dist12 = dist[n-1][m-1].distance % BILLION;
	processGraph(2, BILLION, 1);
	dist21 = dist[n-1][m-1].distance % BILLION;
	dist22 = dist[n-1][m-1].distance / BILLION;
}

long long calculate(int a, int b) {
	DEBUG(
			cerr << a << "/" << b << "->" << dist11 << "/" << dist12 << " or " << dist21 << "/" << dist22 << endl;
	)
	if (a<b || (a==b && dist11 < dist12))
		return ((long long)a)*dist11 + ((long long)b)*dist12;
	else
		return ((long long)a)*dist21 + ((long long)b)*dist22;
	return 0;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin>>n>>m>>k;
	REP(x,n)
		cin>>vertex[x];
	processGraph();
	long long minResult=0x7fffffffffffffffLL, localRes;
	int minCnt=0;
	REP(x,k) {
		cin>>a>>b;
		localRes = calculate(a,b);
		if (localRes < minResult) {
			minResult = localRes;
			minCnt = 1;
		}
		else if (localRes == minResult)
			++minCnt;
	}
	cout << minResult << " " << minCnt;
	return 0;
}