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
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include <bits/stdc++.h>
using namespace std;
#define sim template <class c
#define mor > muu & operator<<(
#define ris return *this
#define R22(r) sim>typename enable_if<1 r sizeof(dud<c>(0)),muu&>::type operator<<(c g) {
#define R23(r) sim, size_t N>typename enable_if<N r std::tuple_size<c>::value,muu&>::type operator<<(zub<c,N> 
sim> struct rge {c b, e;};
sim> rge<c> range(c i, c j) {return rge<c>{i, j};}
sim> auto dud(c*r)->decltype(cerr << *r);
sim> char dud(...);
sim, size_t N> struct zub {c x;};
struct muu {
	#ifdef LOCAL
	#define qel(t) sim, class d, class...e mor t<c,d,e...> r){ris << *(d*)&r;}
	qel(queue) qel(priority_queue) qel(stack)
	stringstream a;
	~muu() {cerr << a.str() << endl;}
	R22(<) a << boolalpha << g; ris;}
	R22(==) ris << range(begin(g), end(g));}
	sim mor rge<c> u) {
		a << "[";
		for (c i = u.b; i != u.e; ++i)
			*this << ", " + 2 * (i == u.b) << *i;
		ris << "]";
	}
	sim, class m mor pair <m,c>r){ris << "(" << r.first << ", " << r.second << ")";}
	sim, class...m mor tuple<c,m...>r){ris << zub<tuple<c,m...>,0>{r};}
	R23(!=) g) {ris << (N ? ", " : "(") << get<N>(g.x) << zub<c, N + 1>{g.x};}
	R23(==) ) {ris << ")";}
	#else
	sim mor const c&){ris;}
	#endif
};
#define imie(r...) "[" #r ": " << (r) << "] "
#define arr(a, i) "[" #a imie(i) ": " << a[i] << "] "
#define range(a, b) "[[" #a ", " #b "): " << range(a, b) << "] "
#define debug muu() << __FUNCTION__ << "#" << __LINE__ << ": "
#define arr2(a, i, j) "[" #a imie(i) imie(j) ": " << a[i][j] << "] "
#define imask(r...) "[" #r ": " << bitset<8 * sizeof(r)>(r) << "] "
using pii = pair <int, int>; using ll = long long; using ull = unsigned long long;
using ld = long double; using Pii = pii; using vpii = vector<pii>; using unt = unsigned int;
using vi = vector <int>; using pll = pair <ll, ll>; using vpll = vector <pll>;
sim> void mini(c &a, c b) {if (a > b) a = b;} sim> void maxi(c &a, c b) {if (a < b) a = b;}
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
sim, class cmp = less<c> > using ordered_set = tree<c, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>; 

int n, m, k;
const int maxn = 2100;
char tab[maxn][maxn];
int dist[maxn][maxn];

void dijikstra()
{
    dist[1][1] = 1;
    //~ priority_queue<array<int, 3>> pq;
    //~ pq.push({-1,1,1});
    vector<vector<Pii>> kolejka(2);
    kolejka[1].push_back({1,1});
    int ind = 1;
    auto jebaj = [&](int x, int y, int p)
    {
        if(tab[x][y] == '.' && (dist[x][y] == 0 || dist[x][y] > p))
        {
            dist[x][y] = p;
            if((int)kolejka.size() <= p)
                kolejka.resize(p+1);
            kolejka[p].push_back({x,y});
            //~ pq.push({-p, x, y});
        }
    };
    while(true)
    {
        if(kolejka[ind].empty())
        {
            ++ind;
            if((int)kolejka.size() == ind)
                break;
        }
        auto tp = kolejka[ind].back();
        kolejka[ind].pop_back();
        int x = tp.first, y = tp.second, pr = ind;
        //~ debug << imie(x) << imie(y) << imie(pr);
        if(dist[x][y] != pr) continue;
        //~ debug << imie(pr);
        jebaj(x, y+1, pr);
        jebaj(x+1,y, pr);
        jebaj(x-1, y, pr+1);
        jebaj(x,y-1, pr+1);
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; ++i)
        scanf("%s", &tab[i][1]);
    dijikstra();
    int odl = dist[n][m] - 1;
    ll minres = 1e18;
    int ile = 0;
    //~ debug << imie(odl);
    for(int i = 0; i < k; ++i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        ll res = 1ll * (n - 1 + m - 1 + odl) * a + 1ll * odl * b;
        if(res < minres)
        {
            minres = res;
            ile = 0;
        }
        if(res == minres)
            ++ile;
    }
    
    //~ for(int i = 1; i <= n; ++i)
        //~ debug << range(tab[i] + 1, tab[i] + m);
    
    //~ for(int i = 1; i <= n; ++i)
        //~ debug << range(dist[i] + 1, dist[i] + m);
    
    printf("%lld %d\n", minres, ile);
}