出题人太菜，暂无测试数据。

题目描述

灰灰家发了大财！他现在购置了一处湖产。他想把湖填平！
但是湖底深度不一。抽象来看，我们假设湖面是一个长$L$宽$W$的长方体，将其划分为$L \times W$个小正方形，如图所示。
每一小格都对应着可能不同的深度。如图，每格上数字对应这格的深度。

现在灰灰有$N$个长方体，第$i$个对应的长宽高分别为$l_i, w_i, h_i$。请你用这些长方体尽可能地填满这个湖，使余下的空间最小。
假设水位不会随填入而上涨，方块可以露出湖面， 但最好不要 。

输入输出格式

输入格式

第一行四个整数$L, W, N, c$，其中$c$表示测试点编号
第$2$~$W+1$行，每行$L$个整数，分别代表每个位置的深度$d_i$
第$W+2$~$W+N+1$行，每行三个整数$l_i, w_i, h_i$

输出格式

共一行一个整数，若填不满则输出剩余空间，刚好填满输出$0$，方块露出湖面则输出漏出来的体积

样例

输入

4 3 6 7
2 2 1 3
2 3 3 3
2 3 3 3
2 3 3
1 1 3
1 1 3
1 1 2
1 1 2
1 1 2

输出

0

数据范围

保证所有数据$L, W, N \leqslant 10000$