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
#include <bits/stdc++.h>
using namespace std;
const int MX=2020,MID=MX*MX,MQ=MID*2;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,-1,0,1};
int n,m,q,A,B,cnt,i,j,x,y,d,fi,fr,qx[MQ],qy[MQ],qz[MQ],dst[MX][MX],cur;
long long dist,res,best=1000000000000000000LL;
char s[MX][MX];
int main() {
  scanf("%d%d%d",&n,&m,&q);
  for (i=0; i<n; i++) scanf("%s",s[i]);
  dst[0][0]=qz[fi=MID]=1;
  for (fr=MID+1; fi<fr; ) {
    i=qx[fi];
    j=qy[fi];
    cur=qz[fi++];
    if (dst[i][j]!=cur) continue;
    for (d=0; d<4; d++) {
      x=i+dx[d];
      y=j+dy[d];
      if (x<0 || x>=n || y<0 || y>=m || s[x][y]=='X') continue;
      cur=dst[i][j]+int(d<2);
      if (dst[x][y]==0 || cur<dst[x][y]) {
        dst[x][y]=cur;
        if (d<2) {
          qx[fr]=x;
          qy[fr]=y;
          qz[fr++]=cur;
        } else {
          qx[--fi]=x;
          qy[fi]=y;
          qz[fi]=cur;
        }
      }
    }
  }
  dist=dst[n-1][m-1]-1;
  while (q--) {
    scanf("%d%d",&A,&B);
    res=(n+m-2LL)*A+dist*(A+B);
    if (res<best) {
      best=res;
      cnt=1;
    } else if (res==best) ++cnt;
  }
  printf("%lld %d\n",best,cnt);
  return 0;
}