Maximize Sum

Limits 1s, 512 MB

You are given two integer arrays AA and BB of length nn and mm respectively. You can do the following operations on array AA.

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

Input

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

The first line contains 33 integers n,m,n, m, and kk.

The second line contains nn integers A1,A2,A3,,AnA_1, A_2, A_3, \ldots, A_n.

The third line contains mm integers B1,B2,B3,,BmB_1, B_2, B_3, \ldots, B_m.

Constraints:

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

Output

For each test case, print the maximum possible value of i=1AAi×i\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 AA, remove 2000000-2000000. After removing, array AA will become [100,10,20,5,500][100, -10, 20, -5, 500].

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

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

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

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

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

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

5×1+4×2+2×3+1×4+100×5+10×6+20×7+5×8+70×9+500×10=6147-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