Quests
Contest: Codeforces Round 916 (Div. 3)
Difficulty rating: 1100
Tags: greedy, math

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_i$$$ experience points;
- for each subsequent completion of the $$$i$$$-th quest, he gets $$$b_i$$$ 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.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 2 \cdot 10^5$$$) — the number of quests and the maximum number of quests Monocarp can complete, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^3$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^3$$$).

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
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.

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Note:
In the first test case, one of the possible quest completion sequences is as follows: $$$1, 1, 2, 3, 2, 4, 4$$$; its total experience is equal to $$$\underline{4} + 1 + \underline{3} + \underline{1} + 1 + \underline{2} + 1 = 13$$$ (the underlined numbers correspond to the instances when we complete a quest for the first time).

In the second test case, one of the possible quest completion sequences is as follows: $$$1, 1$$$; its total experience is equal to $$$\underline{1} + 3 = 4$$$.

In the third test case, one of the possible quest completion sequences is as follows: $$$1, 2, 2, 2, 3$$$; its total experience is equal to $$$\underline{3} + \underline{2} + 3 + 3 + \underline{4} = 15$$$.

Example input:
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

Example output:
13
4
15
15

Editorial:
Let's iterate over the number of quests that have been completed at least once (denote it as $$$i$$$). It remains to complete $$$k-i$$$ quests more, and we are allowed to complete any of the first $$$i$$$ quests again. It is obvious that we would like to complete quests with the largest value of $$$b_i$$$ among the first $$$i$$$ of them. So the answer to the problem is the maximum of $$$\sum\limits_{j=1}^{i} a_j + \max\limits_{j=1}^{i} b_j \cdot (k - i)$$$ over all values of $$$i$$$ from $$$1$$$ to $$$\min(n, k)$$$. Note that the value of $$$n$$$ is too large to calculate sums and maximums in the aforementioned formula every time (for each $$$i$$$ independently), so you have to maintain these values as the value for $$$i$$$ grows.