1757: [模拟][数组]挖湖 [Rob Kolstad, 2008]makelake

    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计算湖中水的体积。

* 第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，为奶牛们依次发动的技能的参数

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

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

342144

usaco