1914C.md (2689B)
1 Source: https://codeforces.com/problemset/problem/1914/C 2 3 C. Quests 4 5 time limit per test 6 7 2.5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 Monocarp can complete quests according to the following rules: 24 25 * the $1$-st quest is always available for completion; 26 * the $i$-th quest is available for completion if all quests $j \lt i$ have been completed at least once. 27 28 Note that Monocarp can complete the same quest multiple times. 29 30 For each completion, the character gets some amount of experience points: 31 32 * for the first completion of the $i$-th quest, he gets $a_i$ experience points; 33 * for each subsequent completion of the $i$-th quest, he gets $b_i$ experience points. 34 35 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. 36 37 Input 38 39 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 40 41 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. 42 43 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^3$). 44 45 The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^3$). 46 47 Additional constraint on the input: the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 48 49 Output 50 51 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. 52 53 Example 54 55 Input 56 57 ``` 58 4 59 60 4 7 61 62 4 3 1 2 63 64 1 1 1 1 65 66 3 2 67 68 1 2 5 69 70 3 1 8 71 72 5 5 73 74 3 2 4 1 4 75 76 2 3 1 4 7 77 78 6 4 79 80 1 4 5 4 5 10 81 82 1 5 1 2 5 1 83 ``` 84 85 Output 86 87 ``` 88 13 89 4 90 15 91 15 92 ``` 93 94 Note 95 96 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). 97 98 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$. 99 100 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$.