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
#include<bits/stdc++.h>

using namespace std;
vector<vector<pair<int,int>>>tab;
string s[2005];
int costs[2005][2005];

void fun(int x, int y, int distance)
{
    if(costs[x][y]==0)
    {
        costs[x][y] = distance;
        tab[distance].push_back(make_pair(x, y));
    }    
}

int main()
{
    int n,m,k;
    long long a,b;
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
        for(int j=0;j<m;j++)
            if(s[i][j]=='X')
            {
                costs[j][i] = -1;
            }
    }
    tab.resize(n*m+1);
    tab[1].push_back(make_pair(0,0));
    costs[0][0]=1;
    int currentX = 0;
    int currentY = 0;
    int currentDistance = 1;
    while(costs[m-1][n-1]==0)
    {
        for(int i=0;i<tab[currentDistance].size();i++)
        {
            currentX = tab[currentDistance][i].first;
            currentY = tab[currentDistance][i].second;
            if(currentX==m-1 and currentY==n-1)
            {
                break;
            }
            if(currentX+1<m)
                fun(currentX+1, currentY, currentDistance+1);
            if(currentY+1<n)
                fun(currentX, currentY+1, currentDistance+1);
            if(currentX!=0)
                fun(currentX-1, currentY, currentDistance+1);
            if(currentY!=0)
                fun(currentX, currentY-1, currentDistance+1);
        }
        currentDistance++;
        //if(tab[currentDistance].size()==0)
        //{
        //    cerr<<"no paths found"<<endl;
        //    return -1;
        //}
    }
    // for(int i=0;i<n;i++)
    // {
    //     for(int j=0;j<m;j++)
    //     {
    //         cerr<<setw(5)<<costs[j][i];
    //     }
    //     cerr<<endl;
    // }
    //cerr<<costs[m-1][n-1]<<endl;
    long long downDistance = (costs[m-1][n-1]-m-n+1)/2;
    long long upDistance = costs[m-1][n-1] - 1 - downDistance;
    cin>>a>>b;
    //cerr<<upDistance<<" "<<downDistance<<" "<<a<<" "<<b<<endl;
    long long minCost = upDistance*a+downDistance*b;
    int numberOfBestHikers=1;
    long long cost;
    for(int i=1;i<k;i++)
    {
        cin>>a>>b;
        cost = upDistance*a+downDistance*b;
        if(cost<minCost)
        {
            //cerr<<"tu"<<endl;
            minCost=cost;
            numberOfBestHikers=1;
        }
        else 
            if(cost==minCost)
                numberOfBestHikers++;
    }
    cout<<minCost<<" "<<numberOfBestHikers<<endl;
    return 0;
}