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
#include <iostream>
#include <queue>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;

/*autor: Agnieszka Klich*/

long long int n, m, k;
int mapa [4000000];

int ileDrog(){
	queue<int> kolejka;
	kolejka.push(0);
	int ruch=0;
	int pole;
	
	do{
		pole = kolejka.front();
		
//		cout <<endl<<"Nowe pole: " << pole<<endl;
		
		kolejka.pop();
		ruch = mapa[pole]+1;
		if(pole==n*m-1) return mapa[n*m-1];
//		cout << "pole: " << pole << "ruch: " << ruch << endl;
		if(pole>m){//mozna isc do gory
//			cout << "gora "<<mapa[pole-m]<<"\n";
			if(mapa[pole-m]==0){
//				cout << "ribie ruch na pole: " << pole-m << "ruch: " << ruch << endl;
				mapa[pole-m]=ruch;
				kolejka.push(pole-m);	
			}
		}
		if(pole<(n-1)*m){//mozna isc na dol
//			cout << "dol "<<mapa[pole+m] <<" \n";
			if(mapa[pole+m]==0){
//				cout << "ribie ruch na pole: " << pole+m << "ruch: " << ruch << endl;
				mapa[pole+m]=ruch;
				kolejka.push(pole+m);	
			}
		}
		if(pole%m!=0 && pole!=1){ //mozna isc w lewo
//			cout << "lewo "<<mapa[pole-1]<<"\n";
			if(mapa[pole-1]==0){
//				cout << "ribie ruch na pole: " << pole-1 << "ruch: " << ruch << endl;
				mapa[pole-1]=ruch;
				kolejka.push(pole-1);	
			}		
		}
		if(pole%m!=m-1){ //mozna isc w prawo
//			cout << "prawo "<<mapa[pole+1]<<"\n";
			if(mapa[pole+1]==0){
//				cout << "ribie ruch na pole: " << pole+1 << "ruch: " << ruch << endl;
				mapa[pole+1]=ruch;
				kolejka.push(pole+1);	
			}
		}
	} while(pole!=n*m-1);
	
	return 0;
}


int main(int argc, char** argv) {
	cin >> n >> m >> k;
	char znak;
	
	for (int i=0; i<n; ++i){
		for(int j=0; j<m; ++j){
			do{
				cin>>znak;
			}while(znak!='.' && znak!='X');
			if(znak=='X')
				mapa[i*m+j] = -1;
			else if(znak='.')
				mapa[i*m+j] = 0;
//			cout <<"Pole:"<<i*m+j<<" Mapa[i*m+j] = "<<mapa[i*n+j] <<endl;
		}
	}
	int ileRuchow = ileDrog();
	
//	cout << "Ile ruchow: "<<ileRuchow<<endl;
	int ileTeoretycznieNajkrocej = n+m-2;
	int ileNaDol = (ileRuchow - ileTeoretycznieNajkrocej)/2;
	int ileDoGory =  ileRuchow - ileNaDol;
	
//	cout << "Ile ruchow: "<<ileRuchow<<" ile na dol: "<<ileNaDol<<" ile do gory: "<<ileDoGory<<endl;
	
	long long int prGora, prDol, czas;
	
	long long int minCzas = 9000000000000000;
	long long int ileOsob = 0;
	
	for(long long int i=0; i<k; ++i){
		cin >> prGora >> prDol;
		czas = prGora*ileDoGory+prDol*ileNaDol;
//		cout << "zawodnik: "<< i <<" czas:" << czas<<endl;
		if(czas<minCzas){
			ileOsob = 0;
			minCzas = czas;
		}
		if(czas==minCzas){
			++ileOsob;
		}
	}
	cout << minCzas <<" "<< ileOsob << "\n";
	
	return 0;
}