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
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define st first
#define nd second
#define pii pair<int,int>
#define mp make_pair
#define pll pair<long long,long long>

using namespace std;

const int nax = 2005;
char a[nax][nax];

int n,m,k;

bool vis[nax][nax];
int odl[nax][nax];

bool ok(int r,int c)
{
    if(r < 1 || c < 1 || r > n || c > m) return false;
    if(vis[r][c]) return false;
    if(a[r][c] == 'X') return false;
    return true;
}

vector<int> dx = {-1,1,0,0};
vector<int> dy = {0,0,-1,1};

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

    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        string s; cin>>s;
        for(int j=1;j<=m;j++)
        {
            a[i][j] = s[j - 1];
        }
    }

    vis[1][1] = true;

    vector<pii> q;
    int wsk = 0;
    q.pb(mp(1,1));
    vis[1][1] = true;
    while(wsk < q.size())
    {
        pii cur = q[wsk];
        wsk++;

        for(int i=0;i<4;i++)
        {
            int x = cur.st + dx[i];
            int y = cur.nd + dy[i];

            if(ok(x,y))
            {
                odl[x][y] = odl[cur.st][cur.nd] + 1;
                vis[x][y] = true;
                q.pb(mp(x,y));
            }
        }
    }

    int od = odl[n][m];


    int ans = 4e18 + 5;
    int cnt = 0;
    while(k--)
    {
        int a,b; cin>>a>>b;

        int ctt = n - 1  + m - 1;

        int cur = (od - ctt) / 2;

        int wa = cur * (a + b);
        wa += ctt * a;

        if(wa < ans)
        {
            ans = wa;
            cnt = 1;
        }
        else if(wa == ans)
        {
            cnt++;
        }
    }

    cout<<ans<<" "<<cnt<<endl;



    return 0;
}