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
#include <iostream>
#include <map>
#include <queue>
#include <set>

char MAP[2000][2000];

int N = 0;
int M = 0;
int K = 0;

struct V {
  V(short x, short y) : x(x), y(y) {}

  bool operator<(const V &o) const {
    return std::tie(x, y) < std::tie(o.x, o.y);
  }

  bool operator==(const V &o) const { return x == o.x && y == o.y; }

  short x;
  short y;
};

struct E {
  E(V v, int a, int b) : v(v), a(a), b(b) {}

  V v;
  int a;
  int b;
};

void wczytajMape() {
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
      char c = 0;
      std::cin >> c;

      MAP[i][j] = (c == '.' ? 1 : 0);
    }
  }
}

void rysujMape() {
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
      std::cout << int(MAP[i][j]);
    }
    std::cout << std::endl;
  }
}

std::pair<int, int> znajdzNajkrotszaSciezke() {
  std::queue<E> fifo;
  std::vector<V> vec = {V(0, 0), V(0, 0), V(0, 0), V(0, 0)};

  fifo.push(E(V(0, 0), 0, 0));

  while (fifo.empty() == false) {
    E e = fifo.front();
    fifo.pop();

    if (e.v == V(M - 1, N - 1)) {
      return {e.a, e.b};
    }

    if (MAP[e.v.y][e.v.x] & 0b10) {
      continue;
    }

    vec[0] = V(e.v.x - 1, e.v.y);
    vec[1] = V(e.v.x + 1, e.v.y);
    vec[2] = V(e.v.x, e.v.y - 1);
    vec[3] = V(e.v.x, e.v.y + 1);

    for (const auto &i : vec) {
      if (i.x < 0 || i.x >= M || i.y < 0 || i.y >= N) {
        continue;
      }
      if ((MAP[i.y][i.x] & 0b01) == 0) {
        continue;
      }

      if (i.x < e.v.x || i.y < e.v.y) {
        fifo.push(E(i, e.a, e.b + 1));
      } else {
        fifo.push(E(i, e.a + 1, e.b));
      }
    }

    MAP[e.v.y][e.v.x] |= 0b10;
  }

  return {-1, -1};
}

int main() {
  std::cin >> N;
  std::cin >> M;
  std::cin >> K;

  wczytajMape();
  // rysujMape();

  //
  auto p = znajdzNajkrotszaSciezke();
  // printf("%d %d\n", p.first, p.second);

  //
  uint64_t min = std::numeric_limits<uint64_t>::max();
  int count = 0;

  for (int i = 0; i < K; ++i) {
    uint64_t a = 0, b = 0;

    std::cin >> a;
    std::cin >> b;

    uint64_t dlugosc = a * p.first + b * p.second;

    if (dlugosc < min) {
      min = dlugosc;
      count = 1;
    } else if (dlugosc == min) {
      count++;
    }
  }

  std::cout << min << " " << count << std::endl;
  return 0;
}