Всесиб

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <math.h>
#include <cmath>
#include <string>
#include <time.h>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <string.h>
#include <stack>
using namespace std;

#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
#define cin in
#define cout out
#define pii pair<int,int>
#define ll long long
#define db double
#define ld long double
#define uset unordered_set
#define umap unordered_map
#define F first
#define S second
#define vec vector
#define ms multiset
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution

ifstream in("input.txt");
ofstream out("output.txt");

const int INF = 2e9;
int n, m, q, xs, ys;

vector<vector<int>> field;
vector<int> vals;
vector<pii> pts;

void input() {
    cin >> n >> m >> q;
    field.resize(n, vector<int>(m));

    cin >> xs >> ys;
    xs--; ys--;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            if (s[j] == '.')
                field[i][j] = 0;
            else
                field[i][j] = INF;
        }
    }

    for (int i = 0; i < q; i++) {
        int x, y, c;
        cin >> x >> y >> c;

        x--; y--;
        vals.push_back(c);
        pts.push_back({ x, y });

        field[x][y] = i+1;
    }
}

struct area {
    int x, y;
    ll val;
};

vector<pii> turns = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };

bool validxy(int x, int y) {
    if (x >= 0 && x < n && y >= 0 && y < m)
        return 1;
    else
        return 0;
}

vector<vector<int>> g;
vector<bool> from_start;

void bfs(int num) {
    vector<vector<bool>> used(n, vector<bool>(m, 0));

    queue<pii> q;
    q.push(pts[num]);
    used[pts[num].first][pts[num].second] = 1;

    while (!q.empty()) {
        pii cur = q.front();
        q.pop();

        int x = cur.first, y = cur.second;

        if (x == xs && y == ys)
            from_start[num] = 1;

        if (field[x][y] != 0 && cur != pts[num]) {
            g[num][field[x][y] - 1] = 1;
            g[field[x][y] - 1][num] = 1;
            continue;
        }

        for (pii turn : turns) {
            int cur_x = x + turn.first;
            int cur_y = y + turn.second;

            if (validxy(cur_x, cur_y) && !used[cur_x][cur_y] && field[cur_x][cur_y] != INF) {
                q.push({ cur_x, cur_y });
                used[cur_x][cur_y] = 1;
            }
        }
    }
}

void transform() {
    from_start.resize(q, 0);
    g.resize(q, vector<int>(q, 0));

    for (int i = 0; i < q; i++)
        bfs(i);
}

bool bit(int a, int pos) {
    return ((a >> pos) % 2);
}

ll cnt(int mask) {
    ll cur = 0;
    for (int i = 0; i < q; i++) {
        if (bit(mask, i))
            cur += vals[i];
    }
    return cur;
}

void dfs(int v, vector<bool>& used, vector<bool> &mask) {
    used[v] = 1;

    for (int to = 0; to < q; to++) {
        if (g[v][to] && !used[to] && mask[to])
            dfs(to, used, mask);
    }
}

bool check(int mask) {
    vector<bool> cur(q, 0);
    for (int i = 0; i < q; i++) {
        if (bit(mask, i))
            cur[i] = 1;
    }

    vector<bool> used(q, 0);
    for (int i = 0; i < q; i++) {
        if (from_start[i] && cur[i])
            dfs(i, used, cur);
    }

    for (int i = 0; i < q; i++) {
        if (!used[i] && cur[i])
            return 0;
    }
    return 1;
}

ll ans = 0;

void gen() {
    for (int i = 0; i < (1 << q); i++) {
        if (check(i)) {
            /*
            for (int j = 0; j < q; j++) {
                if (bit(i, j))
                    cout << j << ' ';
            }
            cout << '\n';
            */

            ans = max(ans, cnt(i));
        }
    }
}

int main() {
    input();
    transform();
    gen();

    cout << ans;
}