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
#include <iostream>
#include <vector>
#include <deque>

struct next {
  next(int a, int b, int dist) : a(a), b(b), dist(dist) {
  }
  int a, b, dist;
};

int main() {
  int n, m, c;
  std::cin >> n >> m >> c;
  std::vector<std::vector<bool>> passable;
  std::vector<std::vector<int>> distance;
  std::deque<next> search;
  
  passable.resize(n);
  distance.resize(n);
  
  std::string row;
  for (int i = 0; i < n; i++) {
    std::cin >> row;
    passable[i].resize(m);
    distance[i].resize(m);
    for (int j = 0; j < m; j++) {
      passable[i][j] = row[j] == '.';
      distance[i][j] = -1;
    }
  }

  passable[0][0] = false;
  search.push_back(next(0, 0, 0));

  while (!search.empty()) {
    next curr = search.front();
    search.pop_front();

    distance[curr.a][curr.b] = curr.dist;
    if (curr.a > 0 && passable[curr.a - 1][curr.b]) {
      search.push_back(next(curr.a - 1, curr.b, curr.dist + 1));
      passable[curr.a - 1][curr.b] = false;
    }
    if (curr.b > 0 && passable[curr.a][curr.b - 1]) {
      search.push_back(next(curr.a, curr.b - 1, curr.dist + 1));
      passable[curr.a][curr.b - 1] = false;
    }
    if (curr.a < n - 1 && passable[curr.a + 1][curr.b]) {
      search.push_back(next(curr.a + 1, curr.b, curr.dist + 1));
      passable[curr.a + 1][curr.b] = false;
    }
    if (curr.b < m - 1 && passable[curr.a][curr.b + 1]) {
      search.push_back(next(curr.a, curr.b + 1, curr.dist + 1));
      passable[curr.a][curr.b + 1] = false;
    }
  }

  long long raw = distance[n - 1][m - 1];
  long long base = n - 1 + m - 1;
  long long up = base + (raw - base) / 2;
  long long down = (raw - base) / 2;
  long long best = 1e18;
  long long count = 0;

  for (int i = 0; i < c; i++) {
    long long a, b;
    std::cin >> a >> b;
    long long time = a * up + b * down;
    if (time < best) {
      best = time;
      count = 1;
    }
    else if (time == best) {
      count++;
    }
  }

  std::cout << best << " " << count << std::endl;

  return 0;
}