F. A Problem You Will Hate More Than Yourself 2
time limit per test
4 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

Whoever tries to solve this problem will either achieve great honor or face terrible failure!

You are given three integers $$$n$$$, $$$x$$$, and $$$y$$$, along with two arrays $$$a$$$ and $$$b$$$, each of length $$$n$$$.

You need to process $$$n$$$ turns. During the $$$i$$$-th turn, you must perform exactly one of the following actions:

  • Increase $$$x$$$ by $$$a_i$$$.
  • Increase $$$y$$$ by $$$a_i$$$.
  • Add $$$x \cdot y \cdot b_i$$$ to your score.

Your initial score is $$$0$$$. Determine the maximum score you can achieve after completing all $$$n$$$ turns.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 10^3$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$x$$$, and $$$y$$$ ($$$1 \leq n, x, y \leq 2*10^3$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2$$$), representing the array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 10^6$$$), representing the array $$$b$$$.

It is guaranteed that the sum of $$$n^2$$$ across all test cases does not exceed $$$4 \cdot 10^6$$$.

Output

For each test case, output in a single line the maximum score you can get.

Example
Input
3
5 1 1
1 1 1 1 1
5 4 3 2 1
4 1 4
1 2 2 2
2 2 2 4
4 2 1
2 1 2 1
9 9 1 5
Output
24
100
114
Note

In the first test case, you can achieve a score of $$$24$$$ as follows:

  1. Increase $$$x$$$ by $$$1$$$.
  2. Increase $$$y$$$ by $$$1$$$.
  3. Add $$$2 \cdot 2 \cdot 3 = 12$$$ to your score.
  4. Add $$$2 \cdot 2 \cdot 2 = 8$$$ to your score.
  5. Add $$$2 \cdot 2 \cdot 1 = 4$$$ to your score.

It can be proven that $$$24$$$ is the maximum score you can achieve.

In the second test case, you can achieve a score of $$$100$$$ as follows:

  1. Increase $$$y$$$ by $$$1$$$.
  2. Increase $$$x$$$ by $$$2$$$.
  3. Increase $$$x$$$ by $$$2$$$.
  4. Add $$$5 \cdot 5 \cdot 4 = 100$$$ to your score.