CF1060C.Maximum Subrectangle

You are given two arrays $a$ and $b$ of positive integers, with length $n$ and $m$ respectively.

Let $c$ be an $n \times m$ matrix, where $c_{i,j} = a_i \cdot b_j$.

You need to find a subrectangle of the matrix $c$ such that the sum of its elements is at most $x$, and its area (the total number of elements) is the largest possible.

Formally, you need to find the largest number $s$ such that it is possible to choose integers $x_1, x_2, y_1, y_2$ subject to $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$, and $$\sum_{i=x_1}^{{x_2}{\sum_{j=y_1}}{y_2}{c_{i,j}}} \leq x.$$

给你两个正整数数组 $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.$$

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 2000$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 2000$).

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($1 \leq b_i \leq 2000$).

The fourth line contains a single integer $x$ ($1 \leq x \leq 2 \cdot 10^{9}$).

第一行包含两个整数 $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}$）。

If it is possible to choose four integers $x_1, x_2, y_1, y_2$ such that $1 \leq x_1 \leq x_2 \leq n$, $1 \leq y_1 \leq y_2 \leq m$, and $\sum_{i=x_1}^{x_2}{\sum_{j=y_1}^{y_2}{c_{i,j}}} \leq x$, output the largest value of $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$ among all such quadruplets, otherwise output $0$.

如果存在四个整数 $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$。

Matrix from the first sample and the chosen subrectangle (of blue color):

Matrix from the second sample and the chosen subrectangle (of blue color):

第一个样例的矩阵以及所选的子矩形（蓝色）：

第二个样例的矩阵以及所选的子矩形（蓝色）：