Little IR12660 arrived in Tecuci, land of legendary mustard sauce. He is currently at a mustard fair, where various mustard sauces are being presented. While the mustard sauces were spinning around on a conveyor belt, he came up with the following idea:
You are given an array $$$A$$$ of length $$$n$$$ and an integer $$$k$$$. You are allowed to perform at most $$$k$$$ cyclic shifts on any subarray of $$$A$$$.
Determine the maximum sum of a contiguous subarray that can be obtained after performing at most $$$k$$$ such cyclic shifts.
A cyclic shift in any direction on a subarray means:
- For a right cyclic shift, the last element of the subarray is moved to the front, and all other elements are shifted one position to the right.
- Example: For $$$A = [1, 2, 3, 4, 5]$$$, a right cyclic shift on the subarray $$$[2, 3, 4]$$$ (indices 2 to 4) results in $$$A = [1, 4, 2, 3, 5]$$$.
- For a left cyclic shift, the first element of the subarray is moved to the back, and all other elements are shifted one position to the left.
- Example: For $$$A = [1, 2, 3, 4, 5]$$$, a left cyclic shift on the subarray $$$[2, 3, 4]$$$ (indices 2 to 4) results in $$$A = [1, 3, 4, 2, 5]$$$.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.
Each test case consists of:
- A single line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^6, k \geq 0, n \cdot k \leq 10^6$$$) — the size of the array and the maximum number of allowed cyclic shifts.
- A second line containing $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — the elements of the array.
It is guaranteed that the sum of $$$n \cdot k$$$ across all testcases does not exceed $$$10^6$$$ and the sum of $$$n$$$ across all testcases does not exceed $$$10^6$$$.
For each test case, output a single integer — the maximum sum of a contiguous subarray that can be obtained after performing at most $$$k$$$ cyclic shifts.
45 2-1 2 -3 4 -57 34 -2 1 3 -1 -3 26 1-1 -1 2 -1 -1 -15 5-1 -1 -1 -1 -1
6 10 2 -1
