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

typedef long long ll;
typedef vector<int> vii;
typedef vector<ll>  vll;
typedef vector<vector<int> > vvi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

vector<vector<pii> > G;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n, m, k;
    cin >> n >> m >> k;

    G.resize(m*n);
    vector<string> mp;

    for(int i = 0 ; i < n; i++){
        string s;
        cin >> s;
        mp.push_back(s);
        for(int j = 1; j < m; j++){
            if(s[j]=='.' && s[j-1]=='.'){
                G[i*m+j].push_back({i*m+j-1, 1});
                G[i*m+j-1].push_back({i*m+j, 0});
            }
        }
    }
    
    for(int i = 1; i < n; i++){
        for(int j = 0; j < m; j++){
            if(mp[i][j]=='.' && mp[i-1][j]=='.'){
                G[i*m+j-m].push_back({i*m+j, 0});
                G[i*m+j].push_back({i*m+j-m, 1});
            }
        }
    }

    vector<int> dist(m*n, -1);

    priority_queue<pii> pq;
    pq.push({0, 0});

    while(!pq.empty()){
        int d = -pq.top().first;
        int u  = pq.top().second;
        pq.pop();
        if(dist[u]!=-1)
            continue;
        dist[u]=d;
        for(auto x : G[u]){
            if(dist[x.first]==-1)
                pq.push({-(d+x.second), x.first});
        }
    }

    int win = 0;
    ll time = (1ll<<50);

    for(int i = 1; i <=k; i++){
        ll a, b;
        cin >> a >> b;
        ll x = ll(m);
        ll y = ll(n);

        ll score = (x+y-2)*a + (a+b)*(ll)dist[m*n-1];

        if(time == score)
            win++;
        if(time>score){
            time = score;
            win = 0;
        }
    }
    cout << time << " " << win+1 << "\n";

}