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
#include<iostream>
#include<vector>
#include<utility>
using namespace std;
long long BFS(vector<vector<long long>>& odl, vector<vector<char>>& plansza, long long dlug, long long szer)
{
	vector<long long> kolejka;
	long long a = 2002 + 1;
	kolejka.push_back(a);
	odl[1][1] = 0;
	long long j = 0;
	long long k = 0;
	long long x;
	long long y;
	while (kolejka.size() > j)
	{
		x = kolejka[j] / 2002;
		y = kolejka[j] % 2002;
		if (x == dlug && y == szer)
			return odl[x][y];
		else
		{
			if ((plansza[x + 1][y] != 'X') && (odl[x + 1][y] == 5000000))
			{
				kolejka.push_back((2002 * (x + 1)) + y);
				odl[x + 1][y] = odl[x][y] + 1;
			}
			if ((plansza[x][y + 1] != 'X') && (odl[x][y + 1] == 5000000))
			{
				kolejka.push_back((2002 * (x)) + y + 1);
				odl[x][y + 1] = odl[x][y] + 1;
			}
			if ((plansza[x - 1][y] != 'X') && (odl[x - 1][y] == 5000000))
			{
				kolejka.push_back((2002 * (x - 1)) + y);
				odl[x - 1][y] = odl[x][y] + 1;
			}
			if ((plansza[x][y - 1] != 'X') && (odl[x][y - 1] == 5000000))
			{
				kolejka.push_back((2002 * (x)) + y - 1);
				odl[x][y - 1] = odl[x][y] + 1;
			}
		}
		j++;
	}
	return 5000000;
}
int main()
{
	long long gora;
	long long dol;
	long long dlug;
	long long szer;
	long long r;
	long long ilo;
	long long min = 5000000000000000;
	long long najszybsi = 0;
	long long wynik;
	vector<vector<char>>plansza;
	vector<char>pomocniczy;
	char pom;
	vector<vector<long long>>odleglosc;
	vector<long long> pomo;
	cin >> dlug >> szer>>ilo;
	for (long long k = 0; k < szer + 2; k++)
	{
		pomocniczy.push_back('X');
		pomo.push_back(5000000);
	}
	plansza.push_back(pomocniczy);
	odleglosc.push_back(pomo);
	pomocniczy.clear();
	pomo.clear();
	for (long long j = 0; j < dlug; j++)
	{
		pomocniczy.push_back('X');
		pomo.push_back(5000000);
		for (long long k = 0; k < szer; k++)
		{
			cin >> pom;
			pomocniczy.push_back(pom);
			pomo.push_back(5000000);
		}
		pomocniczy.push_back('X');
		pomo.push_back(5000000);
		plansza.push_back(pomocniczy);
		odleglosc.push_back(pomo);
		pomocniczy.clear();
		pomo.clear();
	}
	for (long long k = 0; k < szer + 2; k++)
	{
		pomocniczy.push_back('X');
		pomo.push_back(5000000);
	}
	plansza.push_back(pomocniczy);
	odleglosc.push_back(pomo);
	pomocniczy.clear();
	pomo.clear();
	r = (((BFS(odleglosc, plansza,dlug,szer)-dlug)-szer)+2)/2;
	for (long long i = 0; i < ilo; i++)
	{
		cin >> gora >> dol;
		wynik= (r * (gora + dol)) + ((dlug + szer - 2) * gora);
		if (wynik < min)
		{
			min = wynik;
			najszybsi = 1;
		}
		else if (wynik == min)
			najszybsi++;
	}
	cout << min <<" "<< najszybsi;
	return 0;
}