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

int n,m,q;

long long p[2005][2005],d[2005][2005];

char t[2005][2005];

bool odw[2005][2005];

bool bezpieczne(int x,int y)
{
    if(t[x][y] == '.' && !odw[x][y])
        return 1;
    return 0;
}

void Dikstra()
{
    priority_queue< pair<int,pair<int,int> > > Q;
    Q.push({0,{1,1}});
    p[1][1] = d[1][1] = 0;
    while(!Q.empty())
    {
        int x = Q.top().second.first;
        int y = Q.top().second.second;
        int k = Q.top().first * -1;
        Q.pop();
        if(!odw[x][y])
        {
            odw[x][y] = 1;
            if(bezpieczne(x + 1,y) && k + 1 < (p[x + 1][y] + d[x + 1][y] * 2))
            {
                p[x + 1][y] = p[x][y] + 1;
                d[x + 1][y] = d[x][y];
                Q.push({(k + 1) * -1,{x + 1,y}});
            }
            if(bezpieczne(x,y + 1) && k + 1 < (p[x][y + 1] + d[x][y + 1] * 2))
            {
                p[x][y + 1] = p[x][y] + 1;
                d[x][y + 1] = d[x][y];
                Q.push({(k + 1) * -1,{x,y + 1}});
            }
            if(bezpieczne(x - 1,y) && k + 2 < (p[x - 1][y] + d[x - 1][y] * 2))
            {
                p[x - 1][y] = p[x][y];
                d[x - 1][y] = d[x][y] + 1;
                Q.push({(k + 2) * -1,{x - 1,y}});
            }
            if(bezpieczne(x,y - 1) && k + 2 < (p[x][y - 1] + d[x][y - 1] * 2))
            {
                p[x][y - 1] = p[x][y];
                d[x][y - 1] = d[x][y] + 1;
                Q.push({(k + 2) * -1,{x,y - 1}});
            }
        }
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n>>m>>q;
    for(int i = 0;i <= n + 1; i++)
        t[0][i] = t[m + 1][i] = 'X';
    for(int i = 0;i <= m; i++)
        t[i][0] = t[i][n + 1] = 'X';
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j++)
        {
            cin>>t[j][i];
            p[j][i] = 5e6;
            d[j][i] = 5e6;
        }
    Dikstra();
    //cout<<p[m][n]<<" "<<d[m][n]<<'\n';
    long long wyn = 1e18,ile = 0;
    for(int i = 0;i < q; i++)
    {
        int a,b;
        cin>>a>>b;
        long long czas = p[m][n] * a + d[m][n] * b;
        if(czas < wyn)
        {
            wyn = czas;
            ile = 1;
        }
        else if(czas == wyn)
            ile++;
    }
    cout<<wyn<<" "<<ile<<'\n';
    return 0;
}