给定两个正整数数组 $$$a$$$ 和 $$$b$$$,长度分别为 $$$n$$$ 和 $$$m$$$。
令 $$$c$$$ 为 $$$n \times m$$$ 矩阵,其中 $$$c_{i,j} = a_i \cdot b_j$$$。
你需要找到矩阵$$$c$$$的一个子矩形,使其元素之和至多为$$$x$$$,并且其面积(元素总数)尽可能最大。
形式上,您需要找到最大的数字 $$$s$$$,以便可以选择整数 $$$x_1, x_2, y_1, y_2$$$ 并满足 $$$1 \leq x_1 \leq x_2 \leq n$$$, $$$1 \leq y_1 \leq y_2 \leq m$$$, $$$(x_2 - x_1 + 1) \times (y_2 - y_1 + 1) = s$$$,并且 $$$$$$\sum_{i=x_1}^{x_2}{\sum_{j=y_1}^{y_2}{c_{i,j}}} \leq x.$$$$$$
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 2000$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2000$$$)。
第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 2000$$$)。
第四行包含一个整数 $$$x$$$ ($$$1 \leq x \leq 2 \cdot 10^{9}$$$)。
输出
如果可以选择四个整数 $$$x_1, x_2, y_1, y_2$$$ 使得 $$$1 \leq x_1 \leq x_2 \leq n$$$, $$$1 \leq y_1 \leq y_2 \leq m$$$,并且$$$\sum_{i=x_1}^{x_2}{\sum_{j=y_1}^{y_2}{c_{i,j}}} \leq x$$$,输出所有四元组中$$$(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$$$的最大值,否则输出$$$0$$$。
示例
输入 #1
3 3 1 2 3 1 2 3 9
输出 #1
4
输入 #2
5 1 5 4 2 4 5 2 5
输出 #2
1
注意
第一个样本和所选子矩形(蓝色)的矩阵:
第二个样本和所选子矩形(蓝色)的矩阵: