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
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,mmx,abm")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
typedef long long lld;
typedef double lf;
typedef long double llf;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
#define For(i,s,a) for(int i = (int)s; i < (int)a; ++i)
#define rpt(s, it) for(auto it = s.begin(); it != s.end(); ++it)
#define brpt(s, it) for(auto it = s.rend(); it != s.rbegin(); --it)
#define sz size()
#define pb push_back
#define eb emplace_back
#define ff first
#define dd second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ZAPS {int t; scanf("%i", &t); while(t--) solve();}
#define make_unique(x) (x).erase( unique(all(x)), (x).end())


template<typename Ta, typename Tb>
ostream & operator <<(ostream & os, pair<Ta, Tb> x){
	return os << x.ff << " " << x.dd;
}

const int NLIM = 1e3 + 1;

char field[2001][2001];
int odl[2001][2001];

queue<pii>q;

void push_edge(int x, int y, int kier){
	//cout<<x<<" "<<y<<" to "<<kier<<endl;
	switch(kier){
		case 0:
			if(odl[x - 1][y] > odl[x][y] + 1){
				odl[x - 1][y] = odl[x][y] + 1;
				q.push(mp(x - 1, y));
			}
			break;
		case 2:
			if(odl[x + 1][y] > odl[x][y] + 1){
				odl[x + 1][y] = odl[x][y] + 1;
				q.push(mp(x + 1, y));
			}
			break;
		case 1:
			if(odl[x][y + 1] > odl[x][y] + 1){
				odl[x][y + 1] = odl[x][y] + 1;
				q.push(mp(x, y + 1));
			}
			break;
		case 3:
			if(odl[x][y - 1] > odl[x][y] + 1){
				odl[x][y - 1] = odl[x][y] + 1;
				q.push(mp(x, y - 1));
			}
			break;
	}
}

void bfs(int n, int m){
	memset(odl, 0x3f3f3f3f, sizeof(odl[0][0]) * 2001 * 2001);
	q.push({0, 0});
	odl[0][0] = 0;
	while(!q.empty()){
		int x = q.front().ff;
		int y = q.front().dd;
	//	cout<<x<<" "<<y<<" "<<odl[x][y]<<endl;
		q.pop();
		if(x && field[x - 1][y] == '.')
			push_edge(x, y, 0);
		if(x < n - 1 && field[x + 1][y] == '.')
			push_edge(x, y, 2);
		if(y < m - 1 && field[x][y + 1] == '.')
			push_edge(x, y, 1);
		if(y && field[x][y - 1] == '.')
			push_edge(x, y, 3);
	}
}

int32_t main(void){
	int n, m, t;
	scanf("%d%d%d", &n, &m, &t);
	For(i, 0, n)
	scanf("%s", field[i]);
	bfs(n, m);
	lld ile = 0, minx = 1e18;
	lld a = odl[n - 1][m - 1];
	lld b = a = (a - n - m + 2) >> 1;
	while(t--){
		lld x, y;
		scanf("%lld%lld", &x, &y);
		lld cand = (a + n + m - 2) * x + b * y;
		if(minx > cand)
			minx = cand, ile = 1;
		else if(minx == cand)
			++ile;
	}
	printf("%lld %lld", minx, ile);
}

/*
5 7 1
......X
X.X..X.
..X.X.X
.X.X...
.....X.
2 1
*/

/*
2 5 4
.X...
...X.
2 1
2 2
1 7
2 1
*/