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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,k;
int grid[2137][2137];
int dist[2137][2137];
int kx[4]={1,0,-1,0};
int ky[4]={0,-1,0,1};
int main(){
	cin >>n >>m >>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;
			cin >>c;
			if(c=='.')grid[i][j]=1;
		}
	}
	queue<pair<int,int> > q;
	q.push({1,1});
	dist[1][1]=1;
	while(!q.empty()){
		auto pr = q.front();
		q.pop();
		int dis=dist[pr.first][pr.second];
		for(int i=0;i<4;i++){
			int nx=pr.first+kx[i];
			int ny=pr.second+ky[i];
			if(!grid[nx][ny] || dist[nx][ny])continue;
			dist[nx][ny]=dis+1;
			q.push({nx,ny});
		}
	}
	int total = dist[n][m];
//	cout <<total <<"\n";
	int up = n+m-2;
	total -= up + 1;
	up +=total/2;
	int down = total/2;
	//cout <<up <<" " <<down;
	ll best = 1e18;
	int which;
	for(int i=0;i<k;i++){
		ll a,b;
		cin >>a >>b;
		ll here = a*up + b*down;
		if(here < best){
			best = here;
			which=0;
		}
		if(here == best){
			which++;
		}
	}
	cout <<best <<" " <<which;
}