E. Tea Drinking
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are thirsty, and the only thing you can drink is tea. Unfortunately, you hate tea because it is too bitter!

You initially have $$$t$$$ mL of tea and $$$w$$$ mL of fresh water. Because you are thirsty, you must drink exactly $$$s$$$ ($$$1 \le s \le t+w$$$) mL of tea. (You cannot drink fresh water.) You are also given an array $$$B_i$$$ ($$$1 \le i \le t+w$$$) denoting the bitterness you feel when you drink tea.

At any point in time, you can do one of two things:

  • Drink tea. This increases your total bitterness by $$$B_t$$$, then decreases the amount of tea ($$$t$$$) by $$$1$$$ mL.
  • Add fresh water. This decreases your amount of fresh water ($$$w$$$) by $$$1$$$ and increases the amount of tea ($$$t$$$) by $$$1$$$.

Find the minimum total bitterness you can have while drinking enough tea to not be thirsty.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$n$$$ $$$(1 \leq n \leq 1000)$$$. The description of the test cases follows.

The first line of each test case contains three integers $$$t$$$, $$$w$$$, and $$$s$$$ $$$(1 \leq t + w \leq 2 \cdot 10^5, 1 \leq s \leq t+w)$$$.

The second line of input contains $$$t+w$$$ space-separated integers $$$B_1, B_2, ..., B_{t+w}$$$ $$$(1 \leq B_i \leq 10^3)$$$.

The sum of $$$t+w$$$ across all test cases is guaranteed to not exceed $$$2 \cdot 10^5$$$.

—

Tests in subtasks are numbered from $$$1$$$ — $$$20$$$ with samples skipped. Each subtask is worth $$$5$$$ points.

Tests $$$2$$$ — $$$3$$$ satisfy $$$t + w \leq 10$$$ for each test case.

Tests $$$4$$$ — $$$5$$$ satisfy $$$t + w \leq 200$$$ for each test case.

Tests $$$6$$$ — $$$8$$$ satisfy $$$t + w \leq 2 \cdot 10^3$$$ for each test case.

Tests $$$9$$$ — $$$20$$$ satisfy no additional constraints.

Output

For each test case, output the minimum total bitterness you can have while drinking enough tea to not be thirsty.

Example
Input
6
5 0 5
1 2 3 4 5
5 5 3
1 2 3 4 5 6 7 8 9 10
5 5 3
10 9 8 7 6 5 4 3 2 1
1 5 6
1 100 100 100 100 100
5 3 3
100 100 100 100 100 100 100 1
5 3 3
100 100 100 1 100 100 100 100
Output
15
12
6
6
201
102
Note

In the first test case, you have no fresh water, so you must drink all of the tea and have a total bitterness of $$$5 + 4 + 3 + 2 + 1 = 15$$$.

In the second test case, it is optimal to not add any fresh water and only drink tea, for a total bitterness of $$$B_5 + B_4 + B_3 = 5 + 4 + 3 = 12$$$.

In the third test case, it is optimal to add all 5 mL of fresh water before drinking the tea, for a total bitterness of $$$B_{10} + B_9 + B_8 = 1 + 2 + 3 = 6$$$.

An optimal sequence of moves for the sixth test case is as follows:

  • Drink tea, adding $$$B_5 = 100$$$ bitterness (total $$$100$$$) and reducing $$$t$$$ from 5 to 4
  • Drink tea, adding $$$B_4 = 1$$$ bitterness (total $$$101$$$) and reducing $$$t$$$ from 4 to 3
  • Add water, increasing $$$t$$$ from 3 to 4 and reducing $$$w$$$ from 3 to 2
  • Drink tea, adding $$$B_4 = 1$$$ bitterness (total $$$102$$$) and reducing $$$t$$$ from 4 to 3