410698: GYM104077 K 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.

3 4 20
1 3 4
3 1 2
1 3 4 7
4 2 1 2
1
5
6
7
9
10
11
12
15
16
17
22
23
28
30
35
43
47
49
57

0
0
1
1
1
2
2
3
3
4
4
6
6
9
9
12
12
12
18
18