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
122
123
124
125
#pragma GCC optimize("O3")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define BOOST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FOR(a, b, c) for(int a = b; a < c; ++a)
#define PB push_back
#define MP make_pair
#define INF (int)1e9+7
#define LLINF 2e18+7
#define ALL(a) a.begin(), a.end()
#define SIZE(a) (int)a.size()

typedef unsigned long long ULL;
typedef long long LL;
typedef long double LD;

using namespace std;

//#define DEBUG

const int MAX = 2007;

int n, m, k;
bool board[MAX][MAX];
bool vis[MAX][MAX];
int minUp[MAX][MAX];
int minDown[MAX][MAX];

void BFS()
{
    queue <pair <int, int> > bfs;
    bfs.push({0, 0});
    vis[0][0] = 1;

    while(!bfs.empty())
    {
        auto v = bfs.front();
        bfs.pop();

        if(v.first == n - 1 && v.second == m - 1)
            return;

        if(v.first - 1 >= 0 && !board[v.first - 1][v.second] && !vis[v.first - 1][v.second])
        {
            vis[v.first - 1][v.second] = 1;
            minUp[v.first - 1][v.second] = minUp[v.first][v.second];
            minDown[v.first - 1][v.second] = minDown[v.first][v.second] + 1;
            bfs.push({v.first - 1, v.second});
        }

        if(v.second - 1 >= 0 && !board[v.first][v.second - 1] && !vis[v.first][v.second - 1])
        {
            vis[v.first][v.second - 1] = 1;
            minUp[v.first][v.second - 1] = minUp[v.first][v.second];
            minDown[v.first][v.second - 1] = minDown[v.first][v.second] + 1;
            bfs.push({v.first, v.second - 1});
        }

        if(v.first + 1 < n && !board[v.first + 1][v.second] && !vis[v.first + 1][v.second])
        {
            vis[v.first + 1][v.second] = 1;
            minUp[v.first + 1][v.second] = minUp[v.first][v.second] + 1;
            minDown[v.first + 1][v.second] = minDown[v.first][v.second];

            bfs.push({v.first + 1, v.second});
        }

        if(v.second + 1 < m && !board[v.first][v.second + 1] && !vis[v.first][v.second + 1])
        {
            vis[v.first ][v.second + 1] = 1;
            minUp[v.first][v.second + 1] = minUp[v.first][v.second] + 1;
            minDown[v.first][v.second + 1] = minDown[v.first][v.second];
            bfs.push({v.first, v.second + 1});
        }
    }
}

int main()
{
    #ifndef DEBUG
    BOOST;
    #endif

    cin >> n >> m >> k;

    FOR(i, 0, n)
    {
        string s;
        cin >> s;

        FOR(j, 0, m)
        {
            if(s[j] == 'X')
                board[i][j] = 1;
        }
    }

    BFS();

    LL res = LLINF;
    int winners = 0;

    FOR(i, 0, k)
    {
        LL a, b;
        cin >> a >> b;

        LL cost = a * minUp[n - 1][m - 1] + b * minDown[n - 1][m - 1];
    
        if(cost < res)
        {
            res = cost;
            winners = 1;
        }
        else if(cost == res)
        {
            ++winners;
        }
    }

    cout << res << " " << winners << "\n";
 
    return 0;
}