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

void __print(int x) { cerr << x; }
void __print(int64_t x) { cerr << x; }
void __print(uint32_t x) { cerr << x; }
void __print(uint64_t x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template<typename T, typename V>
void __print(const pair<T, V> &x) { cerr << '('; __print(x.first); cerr << ", "; __print(x.second); cerr << ')'; }
template<typename T>
void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; }
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }

const int MAXN = 2005;
const int oo = 1e8;

struct Pos {
    int x, y;
    Pos() : x(0), y(0) {}
    Pos(int _x, int _y) : x(_x), y(_y) {}
    Pos operator+(Pos a) { return Pos(x + a.x, y + a.y); }
};

void __print(const Pos& p) { __print(make_pair(p.x, p.y)); }

struct Dist {
    int64_t a, b;
    Dist() : a(oo), b(oo) {}
    Dist(int64_t _a, int64_t _b) : a(_a), b(_b) {}
};

bool operator<(const Dist& a, const Dist& b) { return a.a + a.b < b.a + b.b; }

struct State {
    Pos p;
    Dist d;
    State(Pos _p, Dist _d) : p(_p), d(_d) {}
};

vector<vector<char>> g(MAXN, vector<char>(MAXN, 'X'));
vector<vector<Dist>> d(MAXN, vector<Dist>(MAXN));
int n, m, k;

const Pos delta[4] = {Pos(-1, 0), Pos(0, -1), Pos(1, 0), Pos(0, 1)};
const Pos start = Pos(1, 1);
Pos finish;

#define debug(x...) cerr << " > [" << #x << "] = ["; _print(x)

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n >> m >> k;
    finish.x = n;
    finish.y = m;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(int j = 0; j < m; j++) {
            g[i + 1][j + 1] = s[j];
        }
    }
    queue<State> q;
    d[start.x][start.y].a = 0;
    d[start.x][start.y].b = 0;
    q.push(State(start, d[start.x][start.y]));
    //debug(g[5][6]);
    while(not q.empty()) {
        State cur = q.front();
        q.pop();
        d[cur.p.x][cur.p.y] = cur.d;
        for(int i = 0; i < 4; i++) {
            Pos next = cur.p + delta[i];
            if(g[next.x][next.y] == 'X') continue;
            Dist d_next = cur.d;
            if(i < 2) d_next.b++;
            else d_next.a++;
            if(d_next < d[next.x][next.y]) {
                d[next.x][next.y] = d_next;
                q.push(State(next, d_next));
            }
        }
    }
    map<int64_t, int> cnt;
    for(int i = 0; i < k; i++) {
        int64_t a, b;
        cin >> a >> b;
        cnt[a * d[finish.x][finish.y].a + b * d[finish.x][finish.y].b]++;
    }
    auto it = cnt.begin();
    cout << it->first << " " << it->second;


    return 0;
}