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;
long long n,m,k;

bool t[2002][2002];
bool odw[2002][2002];
long long x[4] = {1,-1,0,0};
long long y[4] = {0,0,1,-1};
pair<long long,long long> w[8000016];

pair<long long,long long> hx[2002][2002];
pair<long long,long long> hy[2002][2002];
vector<long long>czas;
int main() {
    string s;
    cin>>n>>m>>k;
    for(long long i = 1; i<=n;i++) {
        for(long long j = 1;j<=m;j++) {
            hx[i][j].first=10000000;
            hx[i][j].second=10000000;
            hy[i][j].first=10000000;
            hy[i][j].second=10000000;
        }
    }
    for(long long i = 0; i<n;i++) {
        cin>>s;
        for(long long j = 0;j<m;j++) {
            if(s[j]=='X'){
                t[i+1][j+1]=1;
            }
        }
    }
    for(long long i = 0;i<=n+1;i++)
        t[i][0] = t[i][m+1] = 1;
    for(long long i = 0;i<=m+1;i++)
        t[0][i] = t[n+1][i] = 1;
    //bfs
    long long b = 0; long long e=1;
    w[b]=pair<long long,long long>(1,1);
    hx[1][1].first=0;
    hx[1][1].second=0;
    hy[1][1].first=0;
    hy[1][1].second=0;
    while(b<e) {
        pair<long long,long long> g = w[b++];
      //  cout<<g.first<<" "<<g.second<<"\n";
        for(long long i =0;i<4;i++){
            if(t[g.first+x[i]][g.second+y[i]]!=1 && odw[g.first+x[i]][g.second+y[i]]==false) {
                if(x[i]>0 || y[i]>0) {
                    hx[g.first+x[i]][g.second+y[i]] = hx[g.first][g.second];
                    hx[g.first+x[i]][g.second+y[i]].first++;
                    hy[g.first+x[i]][g.second+y[i]] = hy[g.first][g.second];
                    hy[g.first+x[i]][g.second+y[i]].first++;
                }else{
                    hx[g.first+x[i]][g.second+y[i]] = hx[g.first][g.second];
                    hx[g.first+x[i]][g.second+y[i]].second++;
                    hy[g.first+x[i]][g.second+y[i]] = hy[g.first][g.second];
                    hy[g.first+x[i]][g.second+y[i]].second++;
                }
                odw[g.first+x[i]][g.second+y[i]]=true;
                w[e++]=pair<long long,long long>(g.first+x[i],g.second+y[i]);
              //  cout<<"+";
            }else if (t[g.first+x[i]][g.second+y[i]]!=1) {
                if(x[i]>0 || y[i]>0) {
                    if(hx[g.first+x[i]][g.second+y[i]].first > hx[g.first][g.second].first+1) {
                        hx[g.first+x[i]][g.second+y[i]] = hx[g.first][g.second];
                        hx[g.first+x[i]][g.second+y[i]].first++;
                    }
                 }else{
                    if(hy[g.first+x[i]][g.second+y[i]].second > hy[g.first][g.second].second+1) {
                        hy[g.first+x[i]][g.second+y[i]] = hy[g.first][g.second];
                        hy[g.first+x[i]][g.second+y[i]].second++;
                    }  
                 }
            }
        }
    }
    long long dol,gora;
    for(long long i =0;i<k;i++){
        cin>>dol>>gora;
        czas.push_back( min(dol*hx[n][m].first+gora*hx[n][m].second,dol*hy[n][m].first+gora*hy[n][m].second));
    }
    sort(czas.begin(),czas.end());
    cout<<czas[0]<<" ";
    long long ile = 1;
    for(long long i =1;i<k;i++){
        if(czas[i]!=czas[0])break;
        ile++;
    }
    cout<<ile<<"\n";



    return 0;
}