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
#include <cstdio>
#include <set>
#include <map>
#include <utility>
#include <deque>

int n,m,k;
bool** board;
long** dist;

void read() {
  scanf("%d %d %d\n", &n, &m, &k);
  board = new bool*[n];
  dist = new long*[n];
  for (int i=0; i<n; i++) {
    board[i] = new bool[m];
    dist[i] = new long[m];
  }
  for (int i=0; i<n; i++) {
    for (int j=0; j<m; j++) {
      char c;
      scanf("%c", &c);
      board[i][j] = (c == 'X');
    }
    scanf("\n");
  }
}

void print() {
  for (int i=0; i<n; i++) {
    for (int j=0; j<m; j++) {
      printf("%d", board[i][j]);
    }
    printf("\n");
  }
}

long find_distance() {
  std::deque<std::pair<int, int>> queue;
  queue.emplace_back(0, 0);
  dist[0][0] = 0;

  while (queue.size() > 0) {
    std::pair<int, int> p = queue.front();
    queue.pop_front();
    int i = p.first;
    int j = p.second;
    if (board[i][j] == false) {
      board[i][j] = true;
      //printf("(%d,%d)\n", i, j);
      if (i == n - 1 && j == m - 1) {
        return dist[i][j];
      }
      if (i-1 >= 0 && board[i-1][j] == false) {
        dist[i-1][j] = dist[i][j] + 1;
        queue.emplace_back(i-1, j);
      }
      if (j-1 >= 0 && board[i][j-1] == false) {
        dist[i][j-1] = dist[i][j] + 1;
        queue.emplace_back(i, j-1);
      }
      if (i+1 < n && board[i+1][j] == false) {
        dist[i+1][j] = dist[i][j] + 1;
        queue.emplace_back(i+1, j);
      }
      if (j+1 < m && board[i][j+1] == false) {
        dist[i][j+1] = dist[i][j] + 1;
        queue.emplace_back(i, j+1);
      }
    }
  }
  return -1;
}

int main() {
  read();
  //print();
  long distance = find_distance();
 // printf("distance=%d\n", distance);
  long long opt_cost = -1;
  int opt_count = 0;
  for (int i=0; i<k; i++) {
    long long a, b;
    scanf("%lld %lld", &a, &b);
    long long count_down = (long long) ((distance - (n + m - 2)) / 2);
    long long count_up = distance - count_down;
    
    long long cost = a * count_up + b * count_down;
  //  printf("%lld %lld %lld\n", count_down, count_up, cost);
    if (opt_cost < 0 || cost < opt_cost) {
      opt_cost = cost;
      opt_count = 1;
    } else if (cost == opt_cost) {
      opt_count ++;
    }
  }
  printf("%lld %d\n", opt_cost, opt_count);
  return 0;
}