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
132
133
134
135
136
137
138
139
140
141
#include <bits/stdc++.h>
using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;

#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define dbg(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define fi first
#define se second

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define memclr(x) memset(x, 0, sizeof(x))

#define readRepeatInt int _t_t; cin >> _t_t; while (_t_t--)
#define repeat(i, x) for (int i = 0; i < (x); ++i)
#define repeatRev(i, x) for (int i = (x) - 1; i > 0; --i)

#define retardedRead(x) cin >> x; --x
#define real fixed << setprecision(numeric_limits<double>::digits10 + 1)

#define uns unsigned
                                        using vb = vector<bool>;
using ll =  long long;                  using vll = vector<ll>;
using ull = uns long long;              using vull = vector<ull>;
                                        using vd = vector<double>;
using ld = long double;                 using vld = vector<ld>;
using pi = pair<int, int>;              using vpi = vector<pi>;
using pll = pair<ll, ll>;               using vpll = vector<pll>;
using vi = vector<int>;                 using vvi = vector<vi>;
using si = set<int>;                    using sll = set<ll>;
using usi = unordered_set<int>;         using usll = unordered_set<ll>;
using di = deque<int>;                  using dll = deque<ll>;
using mi = map<int, int>;               using mll = map<ll, ll>;
using umi = unordered_map<int, int>;    using umll = unordered_map<ll, ll>;
using li = list<int>;                   using lll = list<ll>;

template<typename A, typename B> inline A& maxi(A& a, B b) {return a = max(a, b); }
template<typename A, typename B> inline A& mini(A& a, B b) {return a = min(a, b); }

template<typename Iter> inline ostream& streamByIterators(ostream &os, Iter beg, Iter end) {os << '{'; if (beg != end) {os << *beg; while (++beg != end) os << ", " << *beg; }; return os << '}'; }
template<typename T> inline ostream& operator<<(ostream &os, const vector<T> &v) {return streamByIterators(os, v.begin(), v.end()); }
template<typename T> inline ostream& operator<<(ostream &os, const deque<T> &d) {return streamByIterators(os, d.begin(), d.end()); }
template<typename T> inline ostream& operator<<(ostream &os, const set<T> &s) {return streamByIterators(os, s.begin(), s.end()); }
template<typename T, size_t size> inline ostream& operator<<(ostream &os, const array<T, size> &a) {return streamByIterators(os, a.begin(), a.end()); }
template<typename A, typename B> inline ostream& operator<<(ostream &os, const pair<A, B> &p) {return os << '(' << p.first << ", " << p.second << ')'; }

template<typename T, typename V> T constexpr myPow(T base, V exp) {T ans(1); while (exp > 0) {if (exp & 1) ans *= base; base *= base; exp >>= 1; } return ans; }
template<typename T> inline constexpr T myMod(T val, T mod) {val %= mod; if (val < 0) val += mod; return val; }

template<typename T> inline constexpr T min2Pow(T val) {T ret = 1; while (ret < val) ret <<= 1; return ret; }
template<typename T> inline constexpr T max2Div(T val) {return val - (val & (val - 1)); }
template<typename T> inline constexpr int v2(T val) {if (!val) return -1; int ret = 0; while (!(val & 1)) {++ret; val >>= 1; } return ret; }
template<> inline constexpr int v2<int>(int val) {return __builtin_ffs(val) - 1; }

#define endl ENDL FLUSHES
#define pow DOUBLE PRECISION

bool good[2000][2000];
int cost[2000][2000];

vll costsPerContestant;

using pr = pair<int,pi>;

int32_t main()
{
    fastIO;
    
    int n, m, k;
    cin >> n >> m >> k;
    
    char ch;

    repeat(i, n)
    	repeat(j, m)
    	{
    		cin >> ch;
    		if (ch == '.')
    			good[i][j] = true;
    	}
    	
    priority_queue<pr, vector<pr>, greater<pr>> q;
    q.push(pr(1, pi(0,0)));
    
    while(!q.empty())
    {
    	auto [costCurr, coord] = q.top();
    	auto [x, y] = coord;
    	q.pop();
    	if (cost[x][y])
    		continue;
    	cost[x][y] = costCurr;
    	
    	if (x != 0 && good[x-1][y])
    		q.push(pr(costCurr+1, pi(x-1,y)));
    	if (y != 0 && good[x][y-1])
    		q.push(pr(costCurr+1, pi(x,y-1)));
    	if (x != n-1 && good[x+1][y])
    		q.push(pr(costCurr, pi(x+1,y)));
    	if (y != m-1 && good[x][y+1])
    		q.push(pr(costCurr, pi(x,y+1)));
    }
    
    /*repeat(i, n)
    {
    	repeat(j, m)
    	{
    		cout << cost[i][j] << ' ';
    	}
    	cout << '\n';
    }*/
    
    ll costs2 = cost[n-1][m-1] - 1;
    ll costs1 = n+m-2 + costs2;
    
    //cout << dbg(costs1) << dbg(costs2) << '\n';
    	
    costsPerContestant.resize(k);
    
    ll temp1, temp2;
    for (ll& currCost : costsPerContestant)
    {
    	cin >> temp1 >> temp2;
    	currCost = costs1 * temp1 + costs2 * temp2;
    }
    
    sort(all(costsPerContestant));
    
    ll minAns = costsPerContestant.front();
    
    auto it = lower_bound(all(costsPerContestant), minAns + 1);
    
    cout << minAns << ' ' << distance(costsPerContestant.begin(), it);
    

    return 0;
}