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
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long

pair <int, int> ans;
vector <vector <char> > arr;
vector <pair <int, int> > speed;
vector <pair <int, int> > dirs {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int down = INT_MAX, up = INT_MAX, n, m, k;

void DFS(pair <int, int> act, int back, pair <int, int> dir) {
    if (arr[act.f][act.s] == 'X')
        return;
    
    if (back > down)
        return;

    if (act.f == n && act.s == m) {
        if (back < down) 
            down = back;
        return;
    }

    arr[act.f][act.s] = 'X';

    for (auto d : dirs)
        if (d.f + d.s < 0)
            DFS({act.f + d.f, act.s + d.s}, back + 1, d);
        else 
            DFS({act.f + d.f, act.s + d.s}, back, d);

    arr[act.f][act.s] = '.';
}

int main() {
    ios::sync_with_stdio(0);

    cin >> n >> m >> k;
    arr = vector <vector <char> > (n + 2, vector <char> (m + 2, 'X'));
    speed = vector <pair <int, int> > (k);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> arr[i][j];

    for (int i = 0; i < k; i++)
        cin >> speed[i].first >> speed[i].second;
    sort(speed.begin(), speed.end());

    DFS({1, 1}, 0, {1, 0});
    DFS({1, 1}, 0, {0, 1});

    
    ll t = LLONG_MAX;
    int licznik = 0;
    for (auto& s : speed) {
        ll x = (m + n - 2 + down) * s.f + down * s.s;
        if (x < t) {
            t = x;
            licznik = 0;
        }
        if (x == t)
            licznik++;
    }
    cout << t << " " << licznik << "\n";
}