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

char tab[2003][2003];
int n, m;

pair<int, int> odl[2003][2003];
bool odw[2003][2003];
int dx[4] = {1, -1, 0 ,0};
int dy[4] = {0, 0, 1, -1};

void bfs(int x, int y){

    odw[x][y] = true;
    odl[x][y] = {0, 0};

    queue <pair <int, int>> q;
    q.push({x, y});
    
    while (!q.empty()){

        pair <int, int> p = q.front();
        q.pop();

        // cout << p.first << " " << p.second << endl;

        for (int i = 0; i < 4; i ++){

            int nx = p.first + dx[i];
            int ny = p.second + dy[i];

            if (nx >= n || ny >= m) continue;
            if (nx < 0 || ny < 0) continue;
            if (tab[nx][ny] == 'X') continue;
            if (odw[nx][ny]) continue;

            // cout << x << " " << y << " " << nx << " " << ny << "\n";

            if (nx > p.first || ny > p.second) odl[nx][ny] = {odl[p.first][p.second].first + 1, odl[p.first][p.second].second};
            if (nx < p.first || ny < p.second) odl[nx][ny] = {odl[p.first][p.second].first, odl[p.first][p.second].second + 1};

            odw[nx][ny] = true;
            q.push({nx, ny});

        }

    }

}

int main (){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    int k;
    cin >> k;

    for (int i = 0; i < n; i ++){

        for (int j = 0; j < m; j ++){

            cin >> tab[i][j];

        }

    }

    // cout << "hej" << endl;

    bfs(0, 0);

    // cout << "co jes kurwa" << endl;
    // cout << odl[n - 1][m - 1].first << " " << odl[n - 1][m - 1].second << "\n";

    pair <int, int> d = odl[n - 1][m - 1];

    long long mini = 100000000000000000, ile_maks = 0;

    for (int i = 0; i < k; i ++){

        int a, b;
        cin >> a >> b;

        if (1LL * d.first * a + 1LL * d.second * b < mini){
            
            mini = 1LL * d.first * a + 1LL * d.second * b;
            ile_maks = 1;

        }
        else if (1LL * d.first * a + 1LL * d.second * b == mini) ile_maks ++;
        
    }

    cout << mini << " " << ile_maks << "\n";

}