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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <bits/stdc++.h>
using namespace std;

const int nax = 4000000 + 5;
const int INF = 1e9 + 5;

vector <pair <int, bool>> graf[nax];

int dist_wagi[nax];
int dist[nax];

pair <int, int> BFS(int start, int koniec, bool lepsze_wchodzenie)
{
	for(int i = start; i <= koniec; i++)
	{
		dist_wagi[i] = INF;
	}
	
	dist_wagi[start] = 0;
	
	dist[start] = 0;
	
	deque <int> kolejka;
	
	kolejka.push_front(start);
	
	while(!kolejka.empty())
	{
		int wiersz = kolejka.front();
		
		kolejka.pop_front();
		
		for(auto& krawedz : graf[wiersz])
		{			
			int sasiad = krawedz.first;
			int waga = (krawedz.second == lepsze_wchodzenie) ? 0 : 1;
			
			if(dist_wagi[wiersz] + waga < dist_wagi[sasiad])
			{				
				dist_wagi[sasiad] = dist_wagi[wiersz] + waga;
				
				dist[sasiad] = dist[wiersz] + 1;
				
				if(waga == 1)
				{
					kolejka.push_back(sasiad);
				}

				else
				{
					kolejka.push_front(sasiad);
				}
			}
		}		
	}

	return {dist_wagi[koniec], dist[koniec] - dist_wagi[koniec]};
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m, k;
	cin >> n >> m >> k;

	int pole = 1, start = 1, koniec = n * m;

	bool wyzej = true, nizej = false;

	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			char znak;
			cin >> znak;
            
			// wolne pole
			if(znak == '.')
			{
				if(j != m)
				{
					graf[pole].push_back({pole + 1, wyzej});
				}
				
				if(j != 1)
				{
					graf[pole].push_back({pole - 1, nizej});
				}
				
				if(i != n)
				{
					graf[pole].push_back({pole + m, wyzej});
				}
				
				if(i != 1)
				{
					graf[pole].push_back({pole - m, nizej});
				}
			}

			pole++;
		}
	}
	
	// Znajdujemy dwie sciezki i zliczamy poszczegolne kierunki
	// Jedna optymalna dla lewo-prawo i jedna dla gora-dol
	pair <int, int> prawo_dol = BFS(start, koniec, wyzej);
	pair <int, int> lewo_gora = BFS(start, koniec, nizej);
		
	long long minimalny_koszt = LLONG_MAX;
	int ilosc_osob = 0;
	
	for(int i = 0; i < k; i++)
	{
		int koszt_wyzej, koszt_nizej;
		cin >> koszt_wyzej >> koszt_nizej;
		
		long long nowy_koszt;
		
		if(koszt_wyzej > koszt_nizej)
		{
			nowy_koszt = 1LL * koszt_nizej * prawo_dol.first + 1LL * koszt_wyzej * prawo_dol.second;
		}
		
		// koszt_wyzej <= koszt_nizej
		else
		{
			nowy_koszt = 1LL * koszt_wyzej * lewo_gora.first + 1LL * koszt_nizej * lewo_gora.second;
		}
		
		if(nowy_koszt < minimalny_koszt)
		{
			minimalny_koszt = nowy_koszt;
			ilosc_osob = 0;
		}
		
		if(nowy_koszt == minimalny_koszt)
		{
			ilosc_osob++;
		}
	}
	
	cout << minimalny_koszt << " " << ilosc_osob << "\n";
	return 0;
}