I. White Album

时间限制:2s

空间限制:256MB

本题分值:300

题目背景

♪　淡い雪がわたしの　ひそかな想い込めて

純白のアルバムの　ページ　染めてくれる　♪

题目描述

又到了WHITE ALBUM的季节，Setsuna、Kazusa 和 Haruki 三人在旅行途中打起了雪仗。

现在他们正处于 \(n*m\) 大小的区域中，初始时刻，位置 \((i,j)\) 有积雪 \(a_{ij}\) ，而每小时积雪将增加 \(b_{ij}\) 。

他们想找一块 \(r*c\) 的子区域，使得区域内的积雪最多。

给定 \(k\) ，请对于每一个 \(t\in \N,0\le t< k\) ，输出第 \(t\) 小时区域内积雪数量的最大值。一共需要输出 \(k\) 个答案，每个答案
一行。注意，对于每个问题，由于积雪数量变化，你可以选择不同的大小为 \(r*c\) 的区域。

输入格式

第一行两个整数 \(n,m\)，表示区域的大小。

接下来 \(n\) 行，每行 \(m\) 个整数。其中第 \(i\) 行的第 \(j\) 个整数表示 \((i,j)\) 位置的积雪数量 \(a_{ij}\)

接下来 \(n\) 行，每行 \(m\) 个整数。其中第 \(i\) 行的第 \(j\) 个整数表示 \((i,j)\) 位置的积雪增加速度 \(b_{ij}\)

接下来一行三个整数 \(r,c,k\) ，含义见题目描述。

输出格式

共 \(k\) 个整数，每个整数一行，表示答案。

样例输入1

3 3
1 3 5
4 2 10
4 2 1
10 5 7
3 2 4
7 12 9
2 2 2

样例输出1

20
42

样例1解释

第\(0\)小时，积雪情况为：

1 3 5
4 2 10
4 2 1

所以，应当选择以\((1,2)\)为左上角的矩形区域，值最大为\(3+5+2+10=20\)

第\(1\)小时，积雪情况为：

11 8 12
7 4 14
11 14 10

所以，应当选择以\((2,2)\)为左上角的矩形区域，值最大为\(4+14+14+10=42\)

样例输入2

9 10
3695 3506 8994 7981 5277 7829 6280 8193 5267 4687 
6105 1924 819 1200 6324 137 3029 8409 9126 6132 
3168 1008 9766 2060 4550 6683 953 3479 6602 8510 
4310 9421 9295 7865 7415 4443 4522 3898 3464 2820 
8026 259 6090 8449 2929 9460 608 8341 6138 3547 
134 6697 6629 8954 812 5352 8729 9364 396 4251 
6763 3089 5161 3281 7900 7222 3970 6780 5525 207 
7627 7658 5838 7044 6575 1648 9926 4897 1182 5192 
4537 4832 6451 1474 6756 1067 8708 4476 1576 1224 
676 663 374 400 684 770 913 175 588 447 
342 58 559 800 355 247 566 877 263 733 
801 480 363 966 699 809 411 777 727 32 
294 614 226 594 364 606 943 65 989 587 
388 833 497 911 57 901 583 385 149 638 
523 142 420 479 898 889 99 905 114 169 
189 938 788 204 629 808 725 914 126 945 
270 705 688 427 443 845 317 629 136 349 
26 833 442 381 40 986 481 395 650 524 
2 1 15

样例输出2

19061
19650
20285
21601
23420
25239
27058
28877
30696
32515
34334
36153
37972
39791
41610

样例输入3

13 13
4146 4475 5281 2936 8860 3170 1412 7941 4928 7587 4812 1896 3055 
1708 1701 4086 8887 5908 4013 9947 8951 2797 4806 254 6996 1925 
5163 2256 6637 1926 6865 7647 9898 4813 6307 1613 4547 7602 2600 
4587 2677 5620 1952 9641 6922 9257 1355 844 800 7505 882 4347 
3760 9429 8890 9021 1388 3705 2320 5766 6232 5619 3273 8963 9895 
4076 7913 9304 4649 5199 6689 5962 7778 2423 8684 7026 4088 1465 
969 5728 7383 5474 2522 5981 694 5801 705 5564 6826 2094 8698 
1375 8775 6816 9257 7118 2259 8160 6367 1982 2738 1253 2764 8393 
1095 2777 8048 7882 3944 7934 3540 5081 5900 1563 7823 8051 5409 
9283 1740 8104 8892 7589 5184 8756 2169 700 5791 4137 6866 764 
2949 4085 8653 5532 2583 8277 5987 7361 9594 4973 7607 6237 6729 
1909 1956 4607 2419 8704 8342 4492 6547 4467 5694 3342 9124 2328 
6799 2373 4707 7430 5256 6708 1528 9957 8970 3701 2310 7695 1517 
726 315 792 220 622 312 397 965 979 164 510 411 460 
787 974 159 913 627 630 546 290 621 41 635 445 437 
922 944 426 833 71 591 660 258 812 828 769 856 765 
814 689 387 933 948 169 585 106 76 250 157 260 537 
355 992 843 792 760 485 527 747 548 527 71 832 419 
950 176 683 84 878 563 382 943 920 74 268 90 999 
564 607 734 658 633 166 901 970 795 242 478 288 120 
619 215 719 927 482 51 630 764 665 990 110 283 526 
656 996 499 361 209 372 958 570 792 298 160 73 978 
51 377 245 905 731 174 972 450 149 370 594 849 526 
341 732 197 321 378 654 191 626 80 50 849 550 896 
737 737 48 514 728 160 333 540 382 316 736 321 273 
787 654 480 222 59 225 480 506 442 690 92 827 901 
4 10 15

样例输出3

242496
260201
277906
295611
314673
337673
361841
386402
410963
435524
460085
484646
509207
533768
558329

数据范围及限制

对于所有测试点，\(0\le a_{ij}\le 10^{9}, 0\le b_{ij}\le 10^3\)

测试点编号	约定	测试点分值
1~5	\( 1\le n,m\le 10\)，\(1\le r\le n\)，\(1\le c\le m\)，\(k\le 5*10^3\)	每个测试点15分
6~10	\( 1\le n,m\le 10^2\)，\(1\le r\le n\)，\(1\le c\le m\)，\(k\le 5*10^3\)	每个测试点20分
11~15	\( 1\le n,m\le 10^3\)，\(1\le r\le n\)，\(1\le c\le m\)，\(k\le 10^6\)	每个测试点25分

请注意，最终答案可能 不能 用\(32\)位整数表示。