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
///MEMENTO MEMO, MEMENTO LONG LONG
#include <bits/stdc++.h>

#define DEBUG if(0)
#define COUT cout << "\e[36m"
#define ENDL "\e[39m" << endl
#define VAR(v) " [\e[32m" << #v << "\e[36m=\e[91m" << v << "\e[36m] "

using namespace std;
typedef long long LL;

int n, m;

struct Box
{
    bool evil;
    int ad = -1, bd = -1;
};
vector<vector<Box>> carte;

struct XY
{
    int x, y;
};

bool inRange(XY xy)
{
    return (xy.x >= 0 && xy.y >= 0 && xy.x < n && xy.y < m);
}
bool inRange(int x, int y)
{
    return inRange({x,y});
}

void bfs(/*from 0,0*/)
{
    int x4[4] = {1,0,-1,0};
    int y4[4] = {0,1,0,-1};
    int a4[4] = {1,1,0,0};
    int b4[4] = {0,0,1,1};

    queue<XY> que;
    que.push({0,0});
    carte[0][0].ad = 0;
    carte[0][0].bd = 0;
    while(!que.empty())
    {
        XY xy = que.front();
        que.pop();
        //DEBUG COUT << VAR(xy.x) << VAR(xy.y) << ENDL;

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

            if(inRange(xy.x+x4[i], xy.y+y4[i]) &&
            -1 == carte[xy.x+x4[i]][xy.y+y4[i]].ad && !(carte[xy.x+x4[i]][xy.y+y4[i]].evil) )
            {
                carte[xy.x+x4[i]][xy.y+y4[i]].ad = carte[xy.x][xy.y].ad+a4[i];
                carte[xy.x+x4[i]][xy.y+y4[i]].bd = carte[xy.x][xy.y].bd+b4[i];
                que.push({xy.x+x4[i], xy.y+y4[i]});
            }
        }

    }

}

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

    int k;
    cin >> n >> m >> k;
    carte.resize(n, vector<Box>(m));
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j) {
            char ch;
            cin >> ch;
            carte[i][j].evil = (ch == 'X');
        }

    }
    bfs();
    DEBUG COUT << "a:" << carte[n-1][m-1].ad << " b:" << carte[n-1][m-1].bd << ENDL;
    LL ad = carte[n-1][m-1].ad;
    LL bd = carte[n-1][m-1].bd;

    DEBUG
    {
        for(auto el : carte)
        {
            for(auto box : el)
                COUT << setw(2)<<  box.ad << "|" << box.bd << " ";
            COUT << ENDL;
        }

    };

    LL mintime = 1e18;
    int mincnt =0;
    for (int i = 0; i < k; ++i)
    {
        LL a, b;
        cin >> a >> b;

        if(mintime > ad*a+bd*b)
        {
            mintime = ad*a+bd*b;
            mincnt = 0;
        }
        if(mintime == ad*a+bd*b)
        {
            mincnt++;
        }

    }
    cout << mintime << " " <<  mincnt << "\n";

    return 0;
}