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
 96
 97
 98
 99
100
101
#include <bits/stdc++.h>

using namespace std;
#define Vc vector<char>
#define Vint vector<int>
#define LL long long

LL n,m,k;

void addEdge(Vint G[],int i,int n, int m)
{
    //Wszystkie pola poza prawą i dolną krawędzią
    if(i<n*m && i%m!=0 && i<(n*m-m)){
        G[i].push_back(i+1);
        G[i].push_back(i+m);
        G[i+1].push_back(i);
        G[i+m].push_back(i);
    }else if(i<n*m && i%m==0){//Prawa krawedz
        G[i].push_back(i+m);
        G[i+m].push_back(i);
    }else if(i<n*m && i%m!=0){//Dolna krawedz
        G[i].push_back(i+1);
        G[i+1].push_back(i);
    }
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin >> n >> m >> k;
    Vc grid(n*m+1);
    Vint G[n*m+1];
    Vint V(n*m+1,0);

    for(int i=1;i<=n*m;i++){
            cin >> grid[i];
            addEdge(G,i,n,m);
    }

    list<int> q;

    q.push_back(1);
    V[1] = 1;
    int i;
    bool block;
    vector<LL> up(n*m+1),down(n*m+1);

    while(!q.empty()){
        block = 0;
        i=q.front();
        q.pop_front();
        for(auto x : G[i]){
            if(V[x] == 0){
                V[x] = 1;
                if(grid[x] == 'X')
                    continue;
                q.push_back(x);
                if(grid[x] == '.' && x == n*m){
                    if(i-x<0){
                        up[x] = up[i] + 1;
                        down[x] = down[i];
                    }
                    else{
                        down[x] = down[i] + 1;
                        up[x] = up[i];
                    }
                    block = 1;
                }else if(grid[x] == '.'){
                    if(i-x<0){
                        up[x] = up[i] + 1;
                        down[x] = down[i];
                    }
                    else{
                        down[x] = down[i] + 1;
                        up[x] = up[i];
                    }
                }
            }
        }
        if(block)
            break;
    }
    LL a,b;
    LL time;
    LL min_time = 99999999999;
    LL person = 0;
    for(LL i=0;i<k;i++){
        cin >> a >> b;
        time = a*up[n*m] + b*down[n*m];
        if(time < min_time){
            min_time = time;
            person = 1;
        }else if(time == min_time){
            person++;
        }
    }
    cout << min_time << " " << person;
    
    return 0;
}