P9368 [ICPC 2022 Xi'an R] Streets

You are given $n$ vertical lines with x-coordinates $x_1, x_2, \ldots, x_n$ and weights $a_1, a_2, \ldots, a_n$ and $m$ horizontal lines with y-coordinates $y_1, y_2, \ldots, y_m$ and weights $b_1, b_2, \ldots, b_m$. Call a rectangle good if and only if all of its four edges lie on the given lines. On this basis, define the cost of a good rectangle as the sum of the costs of its four segments. The cost of a segment is the product of its length and the weight of the line it belongs. Find the maximum area of good rectangles with cost no more than $c$. Note that the length and the width of the rectangle can be zero, so the answer always exists. You need to answer $T$ queries with different $c$.

The first line contains three integers $n$, $m$ ($2\leq n, m\leq 5\,000$) and $T$ ($1\leq T\leq 100$). The second line contains $n$ integers $x_1, x_2, \ldots, x_n$ ($1\leq x_1 < x_2 < \ldots < x_n \leq 10 ^ 5$). The third line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\leq a_i\leq 10 ^ 7$). The fourth line contains $m$ integers $y_1, y_2, \ldots, y_m$ ($1\leq y_1 < y_2 < \ldots < y_m \leq 10 ^ 5$). The fifth line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($1\leq b_i\leq 10 ^ 7$). Each of the next $T$ lines contains a single integer $c$ ($1\leq c\leq 4\times 10 ^ {12}$), representing a query.

For each query, output one line representing the answer.

**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem K. **Author**: Alex_Wei.