小 S 想买下一块地。他所在的城市可以看成一个 n×m 的网格,要购买所处在 (i,j) 的网格需要缴税 ci,j 元,如果一块地里面有多个网格,则所要缴的税为每个网格需要缴税的和。小 S 手头有 K 块钱,他想知道他最多能够买下多大面积的地,并且想知道所有满足要求的地中缴税最少的一块地所要缴的税。注意他能买的一块地只能是一个矩形。
形式化题意: 有一个 n×m 的矩阵,在 (i,j) 上的元素有一个权值 ci,j,你想知道能够选出权值和 ⩽K 的所有子矩阵中包含最多元素的矩阵的元素个数以及在满足元素个数最大的条件下这个子矩阵中权值和的最小值。
数据范围:t 组数据,1⩽t⩽110,1⩽n,m⩽109,1⩽K⩽109,1⩽ci,j⩽106。
小 S 想买下一块地。他所在的城市可以看成一个 $n\times m$ 的网格,要购买所处在 $(i,j)$ 的网格需要缴税 $c_{i,j}$ 元,如果一块地里面有多个网格,则所要缴的税为每个网格需要缴税的和。小 S 手头有 $K$ 块钱,他想知道他最多能够买下多大面积的地,并且想知道所有满足要求的地中缴税最少的一块地所要缴的税。**注意他能买的一块地只能是一个矩形。**
**形式化题意:** 有一个 $n\times m$ 的矩阵,在 $(i,j)$ 上的元素有一个权值 $c_{i,j}$,你想知道能够选出权值和 $\leqslant K$ 的所有子矩阵中包含最多元素的矩阵的元素个数以及在满足元素个数最大的条件下这个子矩阵中权值和的最小值。
**数据范围:$t$ 组数据,$1\leqslant t\leqslant 110$,$1\leqslant n,m\leqslant 10^9$,$1\leqslant K\leqslant 10^9$,$1\leqslant c_{i,j}\leqslant 10^6$。**