灰灰的湖产

灰灰的湖产

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

题目描述

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

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

输入输出格式

输入格式

第一行四个整数L,W,N,cL, W, N, c,其中cc表示测试点编号
22~W+1W+1行,每行LL个整数,分别代表每个位置的深度did_i
W+2W+2~W+N+1W+N+1行,每行三个整数li,wi,hil_i, w_i, h_i

输出格式

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

样例

输入

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

输出

数据范围

测试点编号 特殊性质
1 L,W,N5L, W, N \leqslant 5且湖底深度相同
2 N100,di1N \leqslant 100, d_i \leqslant 1
3~4 N100,di3N \leqslant 100, d_i \leqslant 3
5 L,W,N100L, W, N \leqslant 100且只有1×1×31 \times 1 \times 3的方块
6~10

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

信息

ID
1038
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者

相关

在下列训练计划中:

灰灰的通天塔 | Huihui‘s Babel