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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <queue>
#include <array>

using namespace std;

#ifdef USE_CERR_LOG
#define LOG if (true) cerr
const bool LogEnabled = true;
#else
#define LOG if (false) cerr
const bool LogEnabled = false;
#endif

bool LogBigEnabled = true;

#ifdef USE_FILE_CIN
ifstream fin("wyc.in");
#define cin fin
#endif

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;

struct Tourist {
    ll timeUp;
    ll timeDown;
};

vector<string> mapa;
vector<Tourist> tourists;
int n, m, k;

void readData() {
    ios_base::sync_with_stdio(false);
    
    cin >> n >> m >> k;
    mapa.resize(n);
    tourists.resize(k);
    
    for (int i = 0; i < n; i++) {
        cin >> mapa[i];
    }
    
    for (int i = 0; i < k; i++) {
        cin >> tourists[i].timeUp >> tourists[i].timeDown;
    }
}

int shortestPath() {
    vector<vector<bool>> visited;
    typedef pair<int, int> Pos;
    queue<Pos> que;
    vector<Pos> diffs = {{-1, 0}, {0, -1}, {0, +1}, {+1, 0}};
    vector<vector<int>> distances;
    
    visited.resize(n);
    distances.resize(n);
        
    for (auto& v : visited) v.resize(m, false);
    for (auto& d : distances) d.resize(m, 0);    
    
    que.push({0, 0});
    visited[0][0] = true;

    while (true) {
        Pos head = que.front();
        que.pop();
        int distance = distances[head.first][head.second];
        
        for (auto dif : diffs) {
            Pos pos = {head.first + dif.first, head.second + dif.second};
            if (pos.first < 0 || pos.first >= n || pos.second < 0 || pos.second >= m || visited[pos.first][pos.second] || mapa[pos.first][pos.second] == 'X') {
                continue;
            }
            
            visited[pos.first][pos.second] = true;
            distances[pos.first][pos.second] = distance + 1;
            
            LOG << pos.first << "," << pos.second << ":" << distances[pos.first][pos.second] << "  ";
            
            que.push(pos);
            
            if (pos.first == n-1 && pos.second == m-1) {
                return distances[pos.first][pos.second];
            }
        }
    }
}

void solve() {
    int distance = shortestPath();
    int base = m + n - 2;
    int extras = (distance - base) / 2;
    int ups = base + extras;
    int downs = extras;
    
    ll minTime = tourists[0].timeUp * ups + tourists[0].timeDown * downs;
    for (auto& t : tourists) {
        minTime = min(minTime, t.timeUp * ups + t.timeDown * downs);
    }
    
    int count = 0;
    for (auto& t : tourists) {
        if (t.timeUp * ups + t.timeDown * downs == minTime) {
            count ++;
        }
    }
    
    cout << minTime << ' ' << count;
}

int main() {
    readData();
    solve();
    return 0;
}