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
#include<bits/stdc++.h>
using namespace std;
long long mini = 1e18;
int licz = 1;
bool odw[2005][2005];
int odl[2005][2005];
char tab[2005][2005];
vector<pair<int,int>> pol = {{-1,0} , {1,0} , {0,1} , {0,-1}};
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    int a,b,c;
    cin>>a>>b>>c;
    for(int x=0;x<=a+1;x++)
        for(int y=0;y<=b+1;y++)
            tab[x][y] = 'X';
    for(int x=1;x<=a;x++)
        for(int y=1;y<=b;y++)
            cin>>tab[x][y];
    queue<pair<int,int>> q;
    q.push(make_pair(1,1));
    odw[1][1] = true;
    while(!q.empty())
    {
        auto p = q.front();
        q.pop();
        for(auto x:pol)
            if(!odw[p.first + x.first][p.second + x.second] && tab[p.first + x.first][p.second + x.second] == '.')
            {
                odw[p.first + x.first][p.second + x.second] = true;
                odl[p.first + x.first][p.second + x.second] = odl[p.first][p.second] + 1;
                q.push(make_pair(p.first + x.first,p.second + x.second));
            }
    }
    while(c--)
    {
        long long d,e;
        cin>>d>>e;
        long long cost = e*(odl[a][b] - (a + b - 2))/2 + d*((odl[a][b] - (a + b - 2))/2 + (a + b - 2));
        if(cost == mini)
            licz++;
        else if(cost < mini)
        {
            mini = cost;
            licz = 1;
        }
    }
    cout<<mini<<" "<<licz;
	return 0;
}