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

#define FOR(i, a, b) for(int i = a; i<b; ++i)
#define FR(a, b) for(int i = a; i>=b;--i)
#define _fastio cin.tie(0); ios_base::sync_with_stdio(0)
#define pb push_back
#define mp make_pair
#define INF 1e18

using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef pair<int, int> iPair;

const int MAX = 3e5 + 2;
const int M = 1e9 +7;

int n, m, k;
bool G[2001][2001];
pair<ll, ll> res[2001][2001];
int nextx[] = {0, 0, -1, 1}, nexty[] = {1, -1, 0, 0};

int main()
{
    _fastio;
    cin>>n>>m>>k;
    FOR(i, 0, n)
        FOR(j, 0, m)
        {
            char c;
            cin>>c;
            if(c == '.')
                G[i][j] = 1;
            res[i][j] = {-1, -1};
        }
    queue<iPair> S;
    S.push({0, 0});
    res[0][0] = {0, 0};
    while(!S.empty())
    {
        int x = S.front().first, y = S.front().second;
        S.pop();
        for(int i = 0; i<4; ++i)
        {
            int xx = x+nextx[i], yy = y+nexty[i];
            if(G[xx][yy] && res[xx][yy].first == -1)
            {
                res[xx][yy] = res[x][y];
                if(i == 0 || i == 3)
                    res[xx][yy].second++;
                else
                    res[xx][yy].first++;
                S.push({xx, yy});
            }
        }
    }
   // cout<<res[n-1][m-1].first<<" "<<res[n-1][m-1].second<<"\n";


    ll mi = INF, cnt = 0;
    while(k--)
    {
        ll a, b;
        cin>>a>>b;
        if(mi > a*res[n-1][m-1].second + b*res[n-1][m-1].first)
        {
            cnt = 1;
            mi = a*res[n-1][m-1].second + b*res[n-1][m-1].first;
        }
        else if(mi == a*res[n-1][m-1].second + b*res[n-1][m-1].first)
            cnt++;
    }
    cout<<mi<<" "<<cnt<<"\n";
}