OI题库

Farmer John想让奶牛们帮他在农场上挖个湖。FJ将他想改造成湖的草地划成了R (3 <= R <= 100)行C (3 <= C <= 100)列，每个格子都是6英尺*6英尺的正方形，并且有个单位为英寸的全格平均高度elev_rc (10 <= elev_rc <= 5000)。

此外，为了他的计划，FJ教会了所有奶牛一项特殊技：战争践踏:)。技能作用范围为3*3的、左上角为R_s,C_s (1 <= R_s <= R-2; 1 <= C_s <= C-2)的正方形区域，效果为把这块区域的地面高度压低D_s (1 <= D_s <= 40)英寸。 不过，技能实际的效果不是很尽人意：事实上，奶牛只能把该区域中高度大于最大高度 - D_s的草地高度压低到最大高度 - D_s，也就是说，区域中可能出现没有被压过的，或者被压低高度小于D_s的格子。

FJ清楚草地上各格子目前的高度，奶牛们发动技能的N (1 <= N <= 20000)个地点，以及挖完湖注完水后的水面高度E (0 <= E <= 5000)。他希望你帮忙计算一下湖中水的总体积（以立方英寸为单位）。这个值保证不超过2,000,000,000。湖周围是一圈很高的堤坝，你不用担 心水会从湖的边缘溢出。

考虑一块将变成湖的4*6的草地。其中每块地的初始高度如下图所示：

                     列编号
                 1  2  3  4  5  6
        第1行:  28 25 20 32 34 36
        第2行:  27 25 20 20 30 34
        第3行:  24 20 20 20 20 30
        第4行:  20 20 14 14 20 20

地图的右上角有一块高地，最高点高度为36，左上角也有个最高点高度为28的土包。第4行中间的地势比较低。在奶牛发动一次参数为“1 4 4”的战争践踏后，草地变成了如下的样子：

                 1  2  3  4  5  6
        第1行:  28 25 20 32 32 32
        第2行:  27 25 20 20 30 32
        第3行:  24 20 20 20 20 30
        第4行:  20 20 14 14 20 20

注意，只有3块草地被压得低了些；其余格子由于本来高度就比较低，根本没有被压过。如果随后FJ指挥奶牛们在左上角发动一次技能，参数为“1 1 10”，技能施放后草地的状态如下：

                 1  2  3  4  5  6
        第1行:  18 18 18 32 32 32
        第2行:  18 18 18 20 30 32
        第3行:  18 18 18 20 20 30
        第4行:  20 20 14 14 20 20
  

如果按设计，湖的水面高度为22英寸，那么草地各部分的水深为：

                 1  2  3  4  5  6
        第1行:   4  4  4 -- -- --
        第2行:   4  4  4  2 -- --
        第3行:   4  4  4  2  2 --
        第4行:   2  2  8  8  2  2

草地上各块水深的和为66。因为每块草地面积为6英尺*6英尺，于是池中水的总体积为66 * 72英寸 * 72英寸 = 342,144立方英寸（1英尺 = 12英寸）。

请你写个程序，帮FJ计算湖中水的体积。

程序名: makelake

输入格式:

• 第1行: 4个用空格隔开的整数：R，C，E，N

• 第2..R+1行: 第i+1行为C个用空格隔开的整数，描述了第i行各列的草地高度

• 第R+2..R+N+1行: 第i+R+1行为3个用空格隔开的整数R_s、C_s、D_s，为奶牛们依次发动的技能的参数

输入样例 (makelake.in):

4 6 22 2
28 25 20 32 34 36
27 25 20 20 30 34
24 20 20 20 20 30
20 20 14 14 20 20
1 4 4
1 1 10

输入说明:

输入即为题中给的例子。

输出格式:

• 第1行: 输出1个整数，为挖好后的湖中水的体积，单位为立方英寸

输出样例 (makelake.out):

342144