# Maximize Sum

National Girls' Programmi...
Limits 1s, 512 MB

You are given two integer arrays $A$ and $B$ of length $n$ and $m$ respectively. You can do the following operations on array $A$.

• Remove one element from $A$. This operation can be performed at most $k$ times.

• Insert any element of $B$ into $A$ at any position. You can insert each element of $B$ at most once.

Output the maximum possible value of $\displaystyle\sum_{i = 1}^{|A|} A_i \times i$ that you can achieve after performing the aforementioned operations.

## Input

Input starts with an integer $T$, denoting the number of test cases. In each test case,

The first line contains $3$ integers $n, m,$ and $k$.

The second line contains $n$ integers $A_1, A_2, A_3, \ldots, A_n$.

The third line contains $m$ integers $B_1, B_2, B_3, \ldots, B_m$.

Constraints:

• $1 \leq T \leq {10}^{4}$

• $1\leq n \leq {10}^{4}$

• $1 \leq m, k \leq 10$

• $-{10}^{9} \leq A_i, B_i \leq {10}^{9}$

It is guaranteed that the sum of $n$ over all test cases does not exceed ${10}^{4}$.

## Output

For each test case, print the maximum possible value of $\displaystyle\sum_{i = 1}^{|A|} A_i \times i$.

## Samples

InputOutput
1
6 5 2
100 -10 20 -2000000 -5 500
-4 -5 -1 -2 70

6147


In the first test case, we shall perform the following operations:

1. From array $A$, remove $-2000000$. After removing, array $A$ will become $[100, -10, 20, -5, 500]$.

2. From array $B$, insert $-1$ at the beginning of array $A$. After inserting, array $A$ will become $[-1, 100, -10, 20, -5, 500]$.

3. From array $B$, insert $-2$ at the beginning of array $A$. After inserting, array $A$ will become $[-2, -1, 100, -10, 20, -5, 500]$.

4. From array $B$, insert $-4$ at the beginning of array $A$. After inserting, array $A$ will become $[-4, -2, -1, 100, -10, 20, -5, 500]$.

5. From array $B$, insert $-5$ at the beginning of array $A$. After inserting, array $A$ will become $[-5, -4, -2, -1, 100, -10, 20, -5, 500]$.

6. From array $B$, insert $70$ at the 8th position of array $A$. After inserting, array $A$ will become $[-5, -4, -2, -1, 100, -10, 20, -5, 70, 500]$.

After completing those operations sequentially, array A gives the maximum result.

$-5\times1 + -4\times2 + -2\times3 + -1\times4 + 100\times5 + -10\times6 + 20\times7 + -5\times8 + 70\times9 + 500\times10 = 6147$

InputOutput
5
4 1 1
-160 -290 -693 -597
38
2 2 3
-149 990
46 48
4 6 2
475 -164 -170 456
59 11 26 -45 -76 -65
6 4 4
997 -711 871 251 617 -306
84 -84 -20 -31
1 5 1
298
-98 -9 -1 -95 -87

-2379
4047
7160
17034
1198