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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define all(a) begin(a),end(a)
#define FOR(x,val,to) for(int x=(val);x<int((to));++x)
#define FORE(x,val,to) for(auto x=(val);x<=(to);++x)
#define FORR(x,arr) for(auto &x: arr)
#define FORS(x,plus,arr) for(auto x = begin(arr)+(plus); x != end(arr); ++x)
#define FORREV(x,plus,arr) for(auto x = (arr).rbegin()+(plus); x !=(arr).rend(); ++x)
#define REE(s_) {cout<<s_<<'\n';exit(0);}
#define GET(arr) for(auto &i: (arr)) sc(i)
#define whatis(x) cerr << #x << " is " << (x) << endl;
#define e1 first
#define e2 second
#define INF 0x7f7f7f7f
typedef std::pair<int,int> pi;
typedef std::vector<int> vi;
typedef std::vector<std::string> vs;
typedef int64_t ll;
typedef uint64_t ull;
#define umap unordered_map
#define uset unordered_set
using namespace std;
using namespace __gnu_pbds;

#ifdef ONLINE_JUDGE
#define whatis(x) ;
#endif
#ifdef _WIN32
#define getchar_unlocked() _getchar_nolock()
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
template<class L, class R> ostream& operator<<(ostream &os, map<L, R> P) { for(auto const &vv: P)os<<"("<<vv.first<<","<<vv.second<<")"; return os; }
template<class T> ostream& operator<<(ostream &os, set<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; }
template<class T> ostream& operator<<(ostream &os, vector<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; }
template<class L, class R> ostream& operator<<(ostream &os, pair<L, R> P) { os<<"("<<P.first<<","<<P.second<<")"; return os; }
inline int fstoi(const string &str){auto it=str.begin();bool neg=0;int num=0;if(*it=='-')neg=1;else num=*it-'0';++it;while(it<str.end()) num=num*10+(*it++-'0');if(neg)num*=-1;return num;}
inline void getch(char &x){while(x = getchar_unlocked(), x < 33){;}}
inline void getstr(string &str){str.clear(); char cur;while(cur=getchar_unlocked(),cur<33){;}while(cur>32){str+=cur;cur=getchar_unlocked();}}
template<typename T> inline bool sc(T &num){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){if(c == EOF) return false;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; return true;}template<typename T, typename ...Args> inline void sc(T &num, Args &...args){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; sc(args...); }
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //s.find_by_order(), s.order_of_key() <- works like lower_bound
template<typename T> using ordered_map = tree<T, int, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 1000001

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m,k;
    sc(n,m,k);
    string a[n];
    FORR(i,a)
        getstr(i);
    /* queue<pi> qu; */
    queue<array<int,3>> qu;
    // set vs vec?
    /* set<pi> st[n][n]; */
    set<pi> st[n][m];
    st[0][0].insert({0,0});
    /* qu.push(0); */
    /* qu.push({0,0}); */
    /* qu.push({0,00}); */
    qu.push({0,0,1});
    // queue -> timer też, of last chg, podobnie jak w dijkstrze
    // -> chg po czasie danego insertu -> continue
    int xdf[] = {1,-1,0,0};
    int ydf[] = {0,0,1,-1};
    int itt = 1;
    int lschg[n][m];
    memset(lschg,0,sizeof lschg);
    while(!qu.empty()){
        /* int v = qu.front(); qu.pop(); */
        /* int crx = qu.front().e1, cry = qu.front().e2; qu.pop(); */
        int crx = qu.front()[0], cry = qu.front()[1], tt = qu.front()[2]; qu.pop();
        /* if(tt < lschg[crx][cry]) */
        if(tt <= lschg[crx][cry])
            continue;
        lschg[crx][cry] = itt;
        ++itt;
        for(int j = 0; j < 4; ++j){
            int nx = crx + xdf[j];
            int ny = cry + ydf[j];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m || a[nx][ny] == 'X')
                continue;
            bool did = 0;
            FORR(i,st[crx][cry]){
                int nf = i.e1 + ((j & 1) ^ 1);
                int ns = i.e2 + (j & 1);
                auto it = st[nx][ny].insert({nf,ns}).e1;
                if(it != st[nx][ny].begin() && prev(it)->e2 <= it->e2){
                    st[nx][ny].erase(it);
                }
                else{
                    /* qu.push({nx,ny}); */
                    // also, nie wiele razy tego samego lol
                    /* qu.push({nx,ny,itt}); */
                    if(!did){
                        qu.push({nx,ny,itt});
                        did = 1;
                    }
                    while(it != --st[nx][ny].end() && next(it)->e2 >= it->e2){
                        st[nx][ny].erase(next(it));
                    }
                }
            }
        }
    }
    /* whatis(st[n-1][m-1]) */
    map<ll,int> mp;
    FOR(i,0,k){
        ll ai,bi;
        sc(ai,bi);
        // da się lepiej niż na pałę?
        // surely, bo ileup - iledol = n - 1 i ileight - ileleft = m - 1
        ll best = LONG_LONG_MAX;
        FORR(x,st[n-1][m-1]){
            best = min(best, ai * x.e1 + bi * x.e2);
        }
        ++mp[best];
    }
    cout << mp.begin()->e1 << ' ' << mp.begin()->e2 << '\n';
}