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 <stdio.h>
#include <queue>

struct pole
{
	int wart;
	int wsp;
	char znak;
};

struct pole mapa[2002][2002];
int n,m,k;


int min(int a, int b)
{
	if(a<b) return a; else return b;
}


void wczytaj_mape()
{
    int x,y;
	char z;

	scanf("%d %d %d\n",&n,&m,&k);
	for(y=1;y<=n;++y)
	  for(x=1;x<=m;++x)
		{
		  if(x==m) scanf("%c\n",&z); else scanf("%c",&z);
		  if (z=='X') mapa[x][y].znak=z; else mapa[x][y].znak=0;
		  mapa[x][y].wsp=2048*y+x;   
		  mapa[x][y].wart=0;
	  	}
	
	return;
}


int opt_path(void)
{
	std::queue<int> kolejka;
	int x,y,r;
	int W;
	
	x=m; y=n;
	if (mapa[x-1][y].znak!='X') kolejka.push(mapa[x-1][y].wsp); 
	if (mapa[x][y-1].znak!='X') kolejka.push(mapa[x][y-1].wsp); 
	mapa[x][y].znak=5;

	while(!kolejka.empty())
	{
		W=kolejka.front();
		kolejka.pop();
		x=W%2048; y=W/2048; 
		r=5000000;
		if(x>1 && mapa[x-1][y].znak>4 && mapa[x-1][y].znak!='X') r=min(r,mapa[x-1][y].wart);
		if(x>1 && mapa[x-1][y].znak!='X' && mapa[x-1][y].znak<4) {kolejka.push(mapa[x-1][y].wsp); mapa[x-1][y].znak++;}
		
		if(x<m && mapa[x+1][y].znak>4 && mapa[x+1][y].znak!='X') r=min(r,mapa[x+1][y].wart);
		if(x<m && mapa[x+1][y].znak!='X' && mapa[x+1][y].znak<4) {kolejka.push(mapa[x+1][y].wsp); mapa[x+1][y].znak++;}	

		if(y>1 && mapa[x][y-1].znak>4 && mapa[x][y-1].znak!='X') r=min(r,mapa[x][y-1].wart);
		if(y>1 && mapa[x][y-1].znak!='X' && mapa[x][y-1].znak<4) {kolejka.push(mapa[x][y-1].wsp); mapa[x][y-1].znak++;}

		if(y<n && mapa[x][y+1].znak>4 && mapa[x][y+1].znak!='X') r=min(r,mapa[x][y+1].wart);
		if(y<n && mapa[x][y+1].znak!='X' && mapa[x][y+1].znak<4) {kolejka.push(mapa[x][y+1].wsp); mapa[x][y+1].znak++;}	

		mapa[x][y].wart=r+1; mapa[x][y].znak=5;
	}

	return mapa[1][1].wart;
}


void rob_reszte(int r)
{
	int a,b,up,down,l;
	long long int t,tmin;

	up=(n+m+r)/2-1; down=r-up;
	tmin=9223372036854775800;
	l=0;
	
	while(k--)
	{
		scanf("%d %d",&a,&b);
		t=(long long int)a * (long long int)up + (long long int)b * (long long int)down;
		if(t<tmin) {l=1; tmin=t;} else if(t==tmin) l++;
	}

	printf("%lld %d\n",tmin,l);

	return;
}




int main()
{
	int x,y;
	
	wczytaj_mape();

	x=opt_path(); 
	rob_reszte(x);

	return 0;
}