给你一个m×n的整数构成1个长方形的数据区域在上面找一个x×y的子区域使子区域中所有元素的和最大。【输入】输入数据的第一行为一个正整数T表示有T组测试数据。每一组测试数据的第一行为四个正整数mnxy0mn1000 AND 0x=m AND 0y=n表示给定的长方形数据区域有m行n列。接下来这个矩阵有m行每行有n个不大于1000的正整数。【输出】对于每组数据输出一个整数表示子区域的最大和。【样例输入

思路：

前缀和

前缀和可以用于处理子矩阵的和，时间复杂度为 $O(1)$。

设 $sum(i,j)$ 表示从 $(1,1)$ 点到 $(i,j)$ 点的矩阵和，那么矩阵 $(x,y)$ 到 $(x+a-1,y+b-1)$ 的和即为：

$$sum(x+a-1,y+b-1)-sum(x-1,y+b-1)-sum(x+a-1,y-1)+sum(x-1,y-1)$$

代码：