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
#include <stdio.h>
#include <map>
#include <climits>

using namespace std;

struct MAP {
  int safe;
  int dist;
  int visited;
};

multimap<int, int> q;
MAP t[2000][2000];  //[m/x][n/y]

void add(int x, int y, int d) {
  if(t[x][y].visited != 0 || t[x][y].safe == 0) {
    return;
  }
  q.insert({d, x*10000+y});
}

int main() {
  int n, m, k;
  long long int a, b;
  char dragons;

  scanf("%d %d %d", &n, &m, &k);
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      scanf(" %c", &dragons);
      t[j][i].safe = (dragons == '.' ? 1 : 0);
      t[j][i].dist = 3000*3000;
      t[j][i].visited = 0;
    }
  }

  add(0, 0, 0);
  while(!q.empty()) {
    int ex = q.begin()->second / 10000;
    int ey = q.begin()->second % 10000;
    int ed = q.begin()->first;
    q.erase(q.begin());
    if(t[ex][ey].visited == 1) {
      continue;
    }
//    printf("visiting %d %d\n", ex, ey);
    t[ex][ey].visited = 1;
    t[ex][ey].dist = ed;
    if(ex+1 < m)  { add(ex+1, ey, ed); }
    if(ex-1 >= 0) { add(ex-1, ey, ed+1); }
    if(ey+1 < n)  { add(ex, ey+1, ed); }
    if(ey-1 >= 0) { add(ex, ey-1, ed+1); }
  }

  long long int time = LLONG_MAX;
  long long int count = 0ll;
  long long int up_times = n + m + t[m-1][n-1].dist - 2LL;
  long long int down_times = t[m-1][n-1].dist;
  for(int i = 0ll; i < k; i++) {
    scanf("%lld %lld", &a, &b);
    long long int est_time = up_times * a + down_times * b;
    if(est_time == time) {
      count++;
    } else if(est_time < time) {
      time = est_time;
      count = 1ll;
    }
  }

//  printf("up=%lld down=%lld\n", up_times, down_times);
  printf("%lld %lld", time, count);
  return 0;
}