You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Monocarp is playing a computer game. In order to level up his character, he can complete quests. There are n quests in the game, numbered from 1 to n.

Monocarp can complete quests according to the following rules:

• the 1-st quest is always available for completion;
• the i-th quest is available for completion if all quests j<i have been completed at least once.

Note that Monocarp can complete the same quest multiple times.

For each completion, the character gets some amount of experience points:

• for the first completion of the i-th quest, he gets a experience points;
• for each subsequent completion of the i-th quest, he gets b experience points.

Monocarp is a very busy person, so he has free time to complete no more than k quests. Your task is to calculate the maximum possible total experience Monocarp can get if he can complete no more than k quests.

Format

Input

The first line contains a single integer tt (1≤t≤10e4) — the number of test cases.

The first line of each test case contains two integers nn and k (1≤n≤2⋅10e5; 1≤k≤2⋅10) — the number of quests and the maximum number of quests Monocarp can complete, respectively.

The second line contains nn integers a1,a2,…,a (1≤ai≤10).

The third line contains nn integers b1,b2,…,b(1≤bi≤10).

Additional constraint on the input: the sum of nn over all test cases does not exceed 2⋅10e5.

Output

For each test case, print a single integer — the maximum possible total experience Monocarp can get if he can complete no more than k quests.

Samples

4
4 7
4 3 1 2
1 1 1 1
3 2
1 2 5
3 1 8
5 5
3 2 4 1 4
2 3 1 4 7
6 4
1 4 5 4 5 10
1 5 1 2 5 1

13
4
15
15

Limitation

time limit per test

2.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output