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 debug if(0)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

typedef long long int ll;

#define MAXN 2048

int n, m, k, a, b;
char plansza[MAXN][MAXN];
queue <pair <int, int> > Q;
bitset <MAXN> odw[MAXN];
int odl[MAXN][MAXN];
ll czas, ile;

pair <int, int> p[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

pair <int, int> operator+(pair <int, int> a, pair <int, int> b) {
    return {a.ff + b.ff, a.ss + b.ss};
}

void Dijkstra() {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            odl[i][j] = 1000000000;
        }
    }
    
    odl[1][1] = 0;
    
    Q.push({1, 1});
    odw[1][1] = true;
    
    while (!Q.empty()) {
        int x = Q.front().ff;
        int y = Q.front().ss;
        Q.pop();
        
        for (int i = 0; i < 4; ++i) {
            if (x + p[i].ff < 1 || y + p[i].ss < 1 || x + p[i].ff > n || y + p[i].ss > m || odw[x + p[i].ff][y + p[i].ss] || plansza[x + p[i].ff][y + p[i].ss] == 'X') {
                continue;
            }
            
            odw[x + p[i].ff][y + p[i].ss] = true;
            odl[x + p[i].ff][y + p[i].ss] = odl[x][y] + 1;
            Q.push({x + p[i].ff, y + p[i].ss});
        }
    }
}

int main() {
    
    scanf ("%d%d%d", &n, &m, &k);
    
    for (int i = 1; i <= n; ++i) {
        scanf ("%s", plansza[i] + 1);
    }
    
    Dijkstra();
    
    debug {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                printf ("i=%d j=%d odl[i][j]=%d\n", i, j, odl[i][j]);
            }
            puts ("");
        }
    }
    
    czas = (ll)(1e18);
    
    for (int i = 1; i <= k; ++i) {
        cin >> a >> b;
        
        ll tmp = (ll)a * (n + m - 2) + (ll)(a + b) * (odl[n][m] - (n + m - 2)) / 2;
        
        if (tmp < czas) {
            czas = tmp;
            ile = 1;
        } else if (tmp == czas) {
            ++ile;
        }
    }
    
    printf ("%lld %lld\n", czas, ile);
    
    return 0;
}
/*
5
2 2
1 1
4 5
7 1
6 7
*/