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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int** map;
vector<vector<pair<int, int>>> route;

void calculateRoute()
{
    int n = route.size();
    int m = route[0].size();
//    cout<<m<<" "<<n<<" <-"<<endl;

    queue<pair<int, int>> queue;
    route[0][0] = pair<int, int>(0,0);
    queue.push(pair<int, int>(0, 0));

    while (!queue.empty())
    {
        pair<int, int> next = queue.front();
        queue.pop();
        int x = next.first;
        int y = next.second;

        if(x + 1 < m and y < n and map[y][x+1] != -1)
        {

            if(route[y][x+1].first + route[y][x+1].second > route[y][x].first + route[y][x].second + 1)
            {
                route[y][x+1].first = route[y][x].first + 1;
                route[y][x+1].second = route[y][x].second;
                queue.push(pair<int, int>(x+1, y));
            }
        }

        if(x < m and y + 1 < n and map[y+1][x] != -1)
        {
            if(route[y+1][x].first + route[y+1][x].second > route[y][x].first + route[y][x].second + 1)
            {
                route[y+1][x].first = route[y][x].first + 1;
                route[y+1][x].second = route[y][x].second;
                queue.push(pair<int, int>(x, y+1));
            }
        }

        if(x < m and y - 1 >= 0 and map[y-1][x] != -1)
        {
            if(route[y-1][x].first + route[y-1][x].second > route[y][x].first + route[y][x].second + 1)
            {
                route[y-1][x].first = route[y][x].first;
                route[y-1][x].second = route[y][x].second + 1;
                queue.push(pair<int, int>(x, y-1));
            }
        }
        if(x - 1 >= 0 and y >= 0 and map[y][x-1] != -1)
        {
            if(route[y][x-1].first + route[y][x-1].second > route[y][x].first + route[y][x].second + 1)
            {
                route[y][x-1].first = route[y][x].first;
                route[y][x-1].second = route[y][x].second + 1;
                queue.push(pair<int, int>(x-1, y));
            }
        }


    }
}

int main()
{
    ios_base::sync_with_stdio(false);

    int n, m, k;

    cin >> n >> m >> k;

    map = new int*[n];
    vector<pair<int, int>> tmp;
    for(int i = 0; i < n; i++)
    {
        route.push_back(tmp);
        map[i] = new int[m];
        for(int j = 0; j < m; j++)
        {
            map[i][j] = 0;
            route[i].push_back(pair<int, int>(5000000,5000000));
        }
    }

    for(int i = 0; i < n; i++)
    {
        char input;
        for(int j = 0; j < m; j++)
        {
            cin >> input;
            map[i][j] = input == '.' ? 1 : -1;
        }
    }
    calculateRoute();
//
    vector<long long> result;
    for(int i = 0; i < k; i++)
    {
        long long a, b;

        cin >> a >> b;
        result.push_back(a * route[n - 1][m - 1].first + b * route[n-1][m-1].second);
    }
    sort(result.begin(), result.end());
    cout<<result[0]<<" ";
    int sum = 0;
    for(int i = 0; i < k; i++)
    {
        if(result[i] == result[0])
            sum++;
        else
            break;
    }
    cout<<sum<<endl;

//    for(int i = 0; i < n; i++)
//    {
//        for(int j = 0; j < m; j++)
//        {
//            cout<<route[i][j].first << ":" << route[i][j].second<< " ";
//        }
////            cout<< map[i][j] << " ";
//        cout<<endl;
//    }

    for(int i = 0; i < n; i++)
    {
        delete [] map[i];
    }
    delete [] map;

    return 0;
}