题目背景

奖品买多了，为了回血，叮叮老师只能摆地摊低价出售奖品😭

题目描述

叮叮老师的摊位是一个n行n列的正方形矩阵，矩阵的每个位置表示当前物品的价格。

此时千夜老师看中了摊位里卖的东西，但是觉得太贵，于是他想了一个办法，他先给叮叮老师k元，然后在摊位里面选择一个m*m大小的矩阵，矩阵中的m*m件物品可以直接带走。

现在，请你帮助千叶老师算一算是否划算，即买到的物品价值是否大于k元。

输入格式

第一行一个整数n。

第二行开始是一个n*n的矩阵，矩阵的每个元素**a[i][j]**表示每个物品的价格。

接下来的一行有两个整数k，m。

输出格式

如果划算输出"YES"，否则输出"NO"。

样例

5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
10 3

NO

5
1 1 1 1 3
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
10 3

YES

数据范围

对于60%的数据$1\le m\le n\le 100$。

对于100%的数据$1\le m\le n\le 1000$。

题目保证数据不会超过int能储存的最大值。

样例解释与提示

对于样例1来说，无论选择哪一个3*3的位置，最多只能获得价值9元的物品，一定是不划算的。

对于样例2来说，可以选择右上角的3*3方格，这样就可以使得总价值大于10，是划算的。

对于前缀和，大家应该并不陌生，对于此题，若想拿到满分，我们需要使用前缀和来优化一下：

对于一维数组a，可以使用sum数组来记录其前缀和：

for(int i=1; i<=n; i++)
{
	cin >> a[i];
	sum[i] = sum[i-1]+a[i];
}

于是

sum[1] = sum[0]+a[1] = a[1]
sum[2] = sum[1]+a[2] = a[1]+a[2]
sum[3] = sum[2]+a[3] = a[1]+a[2]+a[3]
...

若想求l到r之间a数组的和，不必再使用循环嵌套，而是直接使用前缀和数组sum做差：sum[r]-sum[l-1]得到。

若是对于二维数组a，同样我们使用sum来记录前缀和：

for(int i=1; i<=n; i++)
{
	for(int j=1; j<=n; j++)
	{
		sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + a[i][j];
	}
}

若想求一个(x1,y1)到(x2,y2)的矩阵内a数组的和，利用前缀和数组即可在O(1)的时间复杂度内得到：

sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]

具体的推演过程可以参考下面链接里的内容：https://www.cnblogs.com/acioi/p/11705205.html