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
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=2e3+5;
int tab[N][N];
int d[N][N];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m, k;
    cin>>n>>m>>k;
    for(int i=0; i<n; i++){
        string s;
        cin>>s;
        for(int j=0; j<m; j++){
            tab[i][j]=(s[j]=='.');
        }
    }
    vector<pair<int, int> > V;
    V.push_back({0, 0});
    d[0][0]=1;
    while(V.size()){
        for(int i=0; i<V.size(); i++){
            pair<int, int> v=V[i];
            if(v.nd<m-1 && !d[v.st][v.nd+1] && tab[v.st][v.nd+1]){
                d[v.st][v.nd+1]=d[v.st][v.nd];
                V.push_back({v.st, v.nd+1});
            }
            if(v.st<n-1 && !d[v.st+1][v.nd] && tab[v.st+1][v.nd]){
                d[v.st+1][v.nd]=d[v.st][v.nd];
                V.push_back({v.st+1, v.nd});
            }
        }
        vector<pair<int, int> > V2;
        while(V.size()){
            pair<int, int> v=V.back();
            V.pop_back();
            if(v.nd && !d[v.st][v.nd-1] && tab[v.st][v.nd-1]){
                d[v.st][v.nd-1]=d[v.st][v.nd]+1;
                V2.push_back({v.st, v.nd-1});
            }
            if(v.st && !d[v.st-1][v.nd] && tab[v.st-1][v.nd]){
                d[v.st-1][v.nd]=d[v.st][v.nd]+1;
                V2.push_back({v.st-1, v.nd});
            }
        }
        V=V2;
    }
    long long t=d[n-1][m-1]-1;
    //cout<<t<<" ";
    long long M=1e18;
    int ile=0;
    while(k--){
        int a, b;
        cin>>a>>b;
        long long l=a*(t+n+m-2)+b*t;
        if(l<M){
            M=l;
            ile=1;
        }
        else if(l==M)ile++;
    }
    cout<<M<<" "<<ile;
}