8165: BZOJ4165:矩阵

Memory Limit:128 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

定义和谐矩阵为长不小于 Mina 且宽不小于 Minb 的矩阵,矩阵的权值为整个矩阵内所有数的和。给定一个长为 N ,宽为 M 的矩阵 A,求它的所有和谐子矩阵中权值第 K 小的矩阵,并输出它的权值。


输入格式

第 1 行为五个正整数,分别为 N , M , Mina , Minb , K,相邻两个数用一个空格分隔。接下来的 N 行,每行 M  个用一个空格分隔的数,表示给定的矩阵 A。 1 <= N,M <=1000, 1 <= Mina <= N, 1 <= Minb <= M, 1 <= K <= 250000 ,矩阵 A 内每个数均为不超过 3000 的非负整数


输出格式

仅一行,一个数,表示第 K 小矩阵的权值。如果第 K 小矩阵不存在,输出-1。


样例输入

3 4 2 2 3
0 1 3 7
1 16 5 2
7 6 9 3

样例输出

19
【样例解释】
对于第一个样例,最小子矩阵为 3 + 7 + 5 + 2 = 17,次小子矩阵为 0 + 1 + 1 + 16 = 18,
第三小子矩阵为 5 + 2 + 9 + 3 = 19,所以答案为 19。

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: