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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <cstring>

#define REP(a,n) for (int a = 0; a<(n); ++a)
#define FOR(a,b,c) for (int a = (b); a<=(c); ++a)
#define FORD(a,b,c) for (int a = (b); a>=(c); --a)
#define FOREACH(a,v) for (auto a : v)

#define MP make_pair
#define PB push_back

template<class T> inline int size(const T&t) { return t.size(); }

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long LL;

///////////////////////////////

#define INF 1'000'000'000

string tab[2000];
int xs, ys, ile;
int dist[2000][2000];
queue<pair<pii, int>> Q;
LL score[1000000];

inline void wstaw(int y, int x, int d) {
  if (x >= 0 && y >= 0 && x < xs && y < ys && tab[y][x] == '.' && dist[y][x] > d) {
    dist[y][x] = d;
    Q.emplace(MP(y, x), d);
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  cin >> ys >> xs >> ile;
  REP(y, ys) {
    cin >> tab[y];
    REP(x, xs)
      dist[y][x] = INF;
  }
  wstaw(0, 0, 0);
  while (!Q.empty()) {
    int y = Q.front().first.first;
    int x = Q.front().first.second;
    Q.pop();
    wstaw(y + 1, x, dist[y][x] + 1);
    wstaw(y - 1, x, dist[y][x] + 1);
    wstaw(y, x + 1, dist[y][x] + 1);
    wstaw(y, x - 1, dist[y][x] + 1);
  }
  int kor = xs - 1 + ys - 1;
  int dol = (dist[ys - 1][xs - 1] - kor) / 2;
  int gora = dol + kor;
  REP(a, ile) {
    LL g, d;
    cin >> g >> d;
    score[a] = g * gora + d * dol;
  }
  sort(score, score + ile);
  cout << score[0] << " " << upper_bound(score, score + ile, score[0]) - score << endl;
}