Go: // 九九を出すだけ
package main
import (
	"fmt"
	"os"
	"bufio"
)
var out = bufio.NewWriter(os.Stdout)

func main(){
	defer out.Flush()
	for i:=1; i<10; i++{
		for j:=1; j<10; j++{
			fmt.Fprintf(out, "%dx%d=%d\n", i, j, i*j)
		}
	}
}

C++: //============================================================================
// Name        : 3308.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#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 + n;
}
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) //豎よ怙蟆剰エケ逕ィ譌カ霑咎?謾ケ謌薪it[t] < 豁」譌?ゥキ
	{
		return 1;
	}
	return 0;
}
int MinCostFlow(int s, int t, int n) {
	if (s == t) {
		//霑咎?蜈キ菴捺ュ蜀オ蜈キ菴灘?譫撰シ悟ヲよ棡譛蛾刋蜉?霍殳蟆ア荳咲畑?悟ヲよ棡逕ィ謨ー謐ョ荳ュ逧?せ菴應クコs霍殳蟆ア蠕苓?陌?		//逶エ謗・霑泌屓譟蝉クェ蛟シ縲ょ凄蛻冱pfa驥檎噪髦溷?莨壽ュサ蠕ェ邇ッ縲?	}
	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;
		}
	}
	printf("%d %d\n", flow, cost);
	return cost;
}
int main() {
	while (scanf("%d%d%d%d", &R, &C, &n, &k) != EOF) {
		memset(g, -1, sizeof(g));
		th = 0;
		add(0, n + R * C + 1, k, 0);
		for (i = 1; i <= n; i++)
			add(n + R * C + 1, i, 1, 0);
		for (i = 1; i <= R; i++)
			for (j = 1; j <= C; j++)
				scanf("%d", &map[i][j]);
		for (i = 1; i <= n; i++) {
			scanf("%d%d%d", &x, &y, &op);
			add(i, tr(x, y), 1, 0);
			for (t = 0; t < 8; t++) {
				xx = x + dir[t][0];
				yy = y + dir[t][1];
				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]));
				}
			}
		}
		for (i = 1; i <= R; i++)
			for (j = 1; j <= C; j++)
				add(tr(i, j), n + R * C + 2, 1, 0);
		ans = MinCostFlow(0, n + R * C + 2, n + R * C + 3);
		printf("%d\n", ans);
	}
	return 0;
}

C++: #include <iostream>

int main() {
	for (int i = 1; i <= 9; i++)
		for (int j = 1; j <= 9; j++)
			std::cout << i << "x" << j << "=" << i * j << std::endl;
}

C++: #include <iostream>

int main()
{
  for(int i = 1; i < 10; ++i)
    for(int j = 1; j < 10; ++j)
      std::cout << i << "x" << j << "=" << i*j << std::endl;
  return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define FOR(i, s, n) for(int i = s; i < (int)n; i++)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define NCLR(a) memset((a), -1 ,sizeof(a))
#define dump(x) cout << #x << " = " << (x) << "\n";
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n";
#define sq(n) (n) * (n)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
typedef complex<double> P;
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 1000000007;
static const int INF = 1 << 29;
static const LL LL_INF = 1152921504606846976;
static const int dx[] = { -1, 0, 1, 0, 1, -1, 1, -1 };
static const int dy[] = { 0, -1, 0, 1, 1, 1, -1, -1 };


int main() {
#ifdef _DEBUG
	printf( "debug\n" );
#endif
	for ( int i = 1; i < 10; i++ ) {
		for ( int j = 1; j < 10; j++ ) {
			printf( "%dx%d=%d\n", i, j, i * j );
		}
	}
	return 0;
}

C++: #include<stdio.h>

int main ()
{
    for(int i=1;i<10;i++){
            for(int z=1;z<10;z++){
                    printf("%dx%d=%d\n", i, z, i*z);
                    }}
                    
            getchar();return 0;
            }

C++: #include<stdio.h>

int main(void){
	int printf(1x1=1,1x2=2,..9x8=72,9x9=81)

		return 0;
}

C++: #include<iostream

using namespace std;

int main() {

	for(int i = 1; i < 10; i++){
		for(int j = 1; j < 10; j++){
			cont <<  i + "x" + j + "=" (i*j) << endl;
		}
	}

	return 0;

}

C++: #include<stdio.h>
int main()
{
  int t;
  int s;
  for(s=1;s<=9;s=s+1)
    {
      for(t=1;t<=9;t=t+1)
	{
	  printf("%d×%d=%d\n",s,t,s*t);
	}
    }
  return 0;
}

C++: #include<iostream>
using namespace std;

int main()
{
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			cout << i << "*" << j << "=" << i*j << "\n";
		}
	}
    return 0;
}

C++: #include <iostream>
using namespace std;

int main(void)
{
for (int i=1;i<=9;i++)
{
for (int j=1;j<=9;j++)
{
cout << i << "x" << j << "=" << i*j << endl;
}
}
return 0;
}

C++: #include<iostream>
using namespace std;

int main(){
for(int i = 1; i < 10; i++)
for(int j = 1; j< 10; j++)
cout << i << 'x' << j << '=' << i * j << endl;
return 0;
}

C++: #include<stdio.h>
#define f(i,m) for(int i=1;i<=m;i++)
int main(void){
    f(i,9)f(j,9)printf("%d×%d=%d\n",i,j,i*j);
    return 0;
}

C++: #define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#include <bits/stdc++.h>
using namespace std;

int main(){
  for(int i=1;i<10;i++){
    for(int j=1;j<10;j++){
      cout<<i<<"x"<<j<<"="<<i*j<<endl;
    }
  }
  
  return 0;
}

C++: #include<iostream>
using namespace std;

int main(){
 int i,j,k;
 for(i=1;i<=9;i++)
  for(j=1;j<=0;j++)
   printf("%dx%d=%d\n",i,j,i*j);
 

 return 0;
}

C++: #include<iostream>
using namespace std;

int main()
{
	for(int i = 1; i <= 9; i++){
		for(int j = 1; j <= 9; j++){
			cout << i << 'x' << j << '=' << i*j << endl;
		}
	}
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

int main()
{
	for(int i=1; i<=9; i++){
		for(int j=1; j<=9; j++){
			if(i==9&&j==9){
				cout<<i<<'x'<<j<<'='<<i*j;
				break;
			}
			cout<<i<<'x'<<j<<'='<<i*j<<endl;
		}
	}
	return 0;
}