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
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define mp make_pair
int main(){
	long long n,m,k;
	cin>>n>>m>>k;
	int tab[n][m];
	queue<int> kolejka;
	vector<int> G[20000000];
	bool ODW[20000000];
	int C[20000000];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			char a;
			cin>>a;
			if(a=='.'){
				tab[i][j]=1;
			}
			else{
				tab[i][j]=0;
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(tab[i][j]==1){
				if(i-1>=0 && tab[i-1][j]==1){
					G[m*i+j].pb(m*(i-1)+j);
					//cout<<G[m*i+j][0]<<" "<<m*i+j<<endl;
					G[m*(i-1)+j].pb(m*i+j);
					//cout<<G[m*(i-1)+j][0]<<" "<<m*(i-1)+j<<endl;
				}
				if(j-1>=0 && tab[i][j-1]==1){
					G[m*i+j].pb(m*i+j-1);
					G[m*i+j-1].pb(m*i+j);
				}
				if(i+1<n && tab[i+1][j]==1){
					G[m*i+j].pb(m*(i+1)+j);
					G[m*(i+1)+j].pb(m*i+j);
				}
				if(j+1<n && tab[i][j+1]==1){
					G[m*i+j].pb(m*i+j+1);
					G[m*i+j+1].pb(m*i+j);
				}
			}
		}
	}
	int w=0;
	ODW[w]=true;
    	kolejka.push(w);
    	C[w]=0;
    	while(kolejka.empty()==false){
        	int c=kolejka.front();
        	kolejka.pop();
        	int rozmiar=G[c].size();
        	for(int i=0;i<rozmiar;i++){
           		if(ODW[G[c][i]]==false){
                	kolejka.push(G[c][i]);
                	C[G[c][i]]=C[c]+1;
                	ODW[G[c][i]]=true;
            		}
        	}
   	 }
	int wynik=C[m*n-1];
	long long wart[k];
	vector<long long> Q;
	for(int i=0;i<k;i++){
		int d,e;
		cin>>d>>e;
		wart[i]=(m+n-2)*d+((wynik-m-n+2)/2)*(d+e);
	}
	sort(wart,wart+k);
	int i=0;
	while(wart[i]==wart[0]){
		Q.pb(i);
		i++;
	}
	cout<<wart[0]<<" "<<Q.size();
		
					
				
}