F. Tecuci
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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]$$$.
Input

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$$$.

Output

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.

Example
Input
4
5 2
-1 2 -3 4 -5
7 3
4 -2 1 3 -1 -3 2
6 1
-1 -1 2 -1 -1 -1
5 5
-1 -1 -1 -1 -1
Output
6
10
2
-1