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
130
#include <bits/stdc++.h>
 
#define f first
#define s second
#define pb push_back
#define mp make_pair
 
#define ins insert
#define er erase
 
#define siz size()
#define siz1 size()-1
 
#define ll long long
#define ull unsigned long long
#define all(v) v.begin(), v.end()
 
#define FORN(i, n) for(int i=1; i<=(int)n; i++)
#define FOR(i,p,k) for(int i=(int)p; i<=(int)k; i++)
#define FORD(i, k, p) for(int i=(int)k; i>=(int)p; i--)
#define FOR0(i, n) for(int i=(int)n; i>=0; i--)
#define FOR1(i, n) for(int i=(int)n; i>=1; i--)
#define FORV(i, vec) for(auto i = vec.begin(); i != vec.end(); ++i)

#define TURBO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define END cerr<<"TIME: "<<1.0 * clock() / CLOCKS_PER_SEC<<endl;
#define VI vector <int>
#define VP vector <pair<int, int>>
#define VIP vector <pair<int, pair<int, int>>>
#define VPP vector <pair<pair<int, int>, pair<int, int>>>
 
#define MII map<int, int>
#define MLL map<ll, ll>
 
#define PII pair<int, int>
#define PLL pair<ll, ll>
 
#define MAX 1e9 + 10
#define MIN -1e9 + 10

using namespace std;

bool BAD_POINT[2000+10][2000+10];
bool odw[2000+10][2000+10];
int deltas[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
int people_pace[1000000+5][3];
ll results[1000000+5];

int main()
{
	TURBO;
	int n, m, k;
	cin>>n>>m>>k;

	char c;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
		{
			cin>>c;
			if(c == 'X')
				BAD_POINT[i][j] = 1;	
		}
	
	priority_queue <pair<int, PII> > PQ;
	PQ.push({0, {1,1}}); 
	
	bool search_in_progress = 1;
	pair<int, PII> top_element;
	int cost;
	int y, x;
	int neigh_y, neigh_x; 
	int loop_count = 0;
	while (search_in_progress && !PQ.empty())
	{
		top_element = PQ.top();
		PQ.pop();
		
		y = top_element.s.f;
		x = top_element.s.s;
		if (!odw[y][x])
		{
			odw[y][x] = 1;
			cost = top_element.f;

			if (y == n && x == m)
				search_in_progress = 0;
			else
			{
				for(int i=0; i<4; i++)
				{
					neigh_y = y + deltas[i][0];
					neigh_x = x + deltas[i][1];

					if (neigh_y > 0 && neigh_y <= n && neigh_x > 0 && neigh_x <= m && !BAD_POINT[neigh_y][neigh_x] && !odw[neigh_y][neigh_x])
						PQ.push({(cost-1), {neigh_y, neigh_x}});
				}	
			}
		}
	}
	
	ll llcost = cost*(-1);
	ll best_result = LLONG_MAX;
	ll num_slow, num_fast;

	num_slow = n + m - 2;
	llcost -= num_slow;
	llcost /= 2;

	num_slow += llcost;
	num_fast = llcost;

	ll result;
	for(int i=1; i<=k; i++)
	{
		cin>>people_pace[i][0]>>people_pace[i][1];
		results[i] = num_slow * people_pace[i][0] + num_fast * people_pace[i][1];
		best_result = min(results[i], best_result);
	}

	cout<<best_result<<' ';

	int counter = 0;
	for(int i=1; i<=k; i++)
		if (results[i] == best_result)
			counter++;

	cout<<counter;	
	
	return 0;
}