#include <iostream>#include <stdio.h>#include <stdlib.h>#include<memory.h>using namespace std;#define M 200001#define maxx 2000#define Max(a, b) a > b ? a : b#define Min(a, b) a < b ? a : b#define inf (1 << 29)struct T {int u, v, val, next, cost;} e[M];int th;int visit[M], pre[M], dis[M], que[M], g[M], pos[M], map[100][100];int R, C, n, k, i, j, x, y, op, t, xx, yy, ans;int dir[8][2] = { { -1, -2 }, { -2, -1 }, { 1, -2 }, { -2, 1 }, { -1, 2 }, { 2,-1 }, { 1, 2 }, { 2, 1 } };int tr(int x, int y) {return (x - 1) * C + y;}void add(int u, int v, int val, int cost) {e[th].u = u, e[th].v = v, e[th].val = val, e[th].cost = cost;e[th].next = g[u], g[u] = th++;e[th].u = v, e[th].v = u, e[th].val = 0, e[th].cost = -cost;e[th].next = g[v], g[v] = th++;}int spfa(int s, int t, int n) {int i, v, k;for (i = 0; i <= n; i++) {pre[i] = -1, visit[i] = 0;}int head, tail;head = tail = 0;for (i = 0; i <= n; i++)dis[i] = inf;que[tail++] = s, pre[s] = s, dis[s] = 0, visit[s] = 1;while (head != tail) {int u = que[head++];visit[u] = 0;for (k = g[u]; k != -1; k = e[k].next) {v = e[k].v;if (e[k].val > 0 && dis[u] + e[k].cost < dis[v]) {dis[v] = dis[u] + e[k].cost;pre[v] = u;pos[v] = k;if (!visit[v]) {visit[v] = 1;que[tail++] = v;}}}}if (pre[t] != -1 && dis[t] < inf) {return 1;}return 0;}int MinCostFlow(int s, int t, int n) {if (s == t) {}int flow = 0, cost = 0;while (spfa(s, t, n)) {int u, min = inf;for (u = t; u != s; u = pre[u]) {min = Min(min, e[pos[u]].val);}flow += min;cost += dis[t] * min;for (u = t; u != s; u = pre[u]) {e[pos[u]].val -= min;e[pos[u] ^ 1].val += min;}}if (flow<k) cost=-1;return cost;}int main() {while (scanf("%d%d%d%d", &R, &C, &n, &k) != EOF) {memset(g, -1, sizeof(g));th = 0;add(0, R * C + 1, k, 0);for (i = 1; i <= R; i++)for (j = 1; j <= C; j++) {scanf("%d", &map[i][j]);if ((i + j) % 2)add(tr(i, j), R * C + 2, 1, 0);}for (i = 1; i <= n; i++) {scanf("%d%d%d", &op, &x, &y);add(R * C + 1, tr(x, y), 1, 0);for (t = 0; t < 8; t++) {xx = x + dir[t][0];yy = y + dir[t][1];if (xx >= 1 && xx <= R && yy >= 1 && yy <= C) {if (op == 1) {add(tr(x, y), tr(xx, yy), 1, map[x][y] * map[xx][yy]);}if (op == 2) {add(tr(x, y), tr(xx, yy), 1, map[x][y] + map[xx][yy]);}if (op == 3) {add(tr(x, y), tr(xx, yy), 1,max(map[x][y], map[xx][yy]));}}}}ans = MinCostFlow(0, R * C + 2, R * C + 3);printf("%dn", ans);}return 0;}
