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

题目描述

灰灰家发了大财！他现在购置了一处湖产。他想把湖填平！
但是湖底深度不一。抽象来看，我们假设湖面是一个长\(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

数据范围

测试点编号	特殊性质
1	\(L, W, N \leqslant 5\)且湖底深度相同
2	\(N \leqslant 100, d_i \leqslant 1\)
3~4	\(N \leqslant 100, d_i \leqslant 3\)
5	\(L, W, N \leqslant 100\)且只有\(1 \times 1 \times 3\)的方块
6~10	无

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