409659: GYM103660 L Monster Tower

To be The Elden Lord, The Tarnished will face many challenges. Here comes one.

There is a monster tower of height $$$n$$$, the strength of the monster on the $$$i$$$-th floor is $$$a_i$$$. The initial strength of The Tarnished is $$$x$$$.

For any moment, The Tarnished can choose some monster not stronger than him from the lowest $$$k$$$ floors, and kill it. After The Tarnished kills the monster on the $$$i$$$-th floor$$$(1 \le i \le k,\ a_i \le x)$$$, his strength increases by $$$a_i$$$, and the $$$i$$$-th floor will disappear. So all floors higher than the $$$i$$$-th floor will fall, the original $$$(i+1)$$$-th floor become the $$$i$$$-th floor, $$$(i+2)$$$-th becomes $$$(i+1)$$$-th, and so on.

Now, the problem is what is the minimum $$$x$$$ to kill all monsters in this tower.

The first line contains a single integer $$$T(1 \le T \le 2 \times 10^5)$$$ — the number of test cases.

The first line of each test case contains two integers $$$n(1 \le n \le 2 \times 10^5)$$$ and $$$k(1\le k\le n)$$$ — the height of the tower and the highest floor that The Tarnished can reach respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots ,a_n(1 \le a_i \le 10^9)$$$ — the strength of each monster.

It is guaranteed that $$$\sum n\le 2\times 10^5$$$ over all test cases.

For each test case, output a single integer — the minimum $$$x$$$ to kill all monsters.

2
3 2
1 10 5
3 1
1 10 5

4
9

In the first test case, The Tarnished kills the monster on the first floor, so his strength becomes $$$5$$$, and the third floor becomes the second floor so The Tarnished can reach it and kill the monster. After that, his strength becomes $$$10$$$ and can kill the last one.