A. K Is Important
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ consisting of $$$n$$$ positive integers, as well as an integer parameter $$$k$$$.

While the array has at least $$$k$$$ elements, you need to perform one of the following two types of operations on $$$a$$$:

  • Remove $$$a_k$$$ and add its value to your score, or
  • Remove $$$a_{m-k+1}$$$ and add its value to your score, where $$$m$$$ is the length of $$$a$$$ before this operation.

After removing an element, the remaining elements keep their relative order.

Your task is to determine the maximum possible score that can be obtained.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^5$$$) — the length of $$$a$$$ and the parameter.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output a single integer — the maximum score that can be obtained.

Example
Input
4
4 2
1 2 3 4
4 4
3 4 1 2
1 1
1
6 3
1 4 8 2 6 3
Output
9
3
1
19
Note

In the first test case, we can first remove $$$a_3 = 3$$$. The score becomes $$$3$$$, and the array becomes $$$[1, 2, 4]$$$. Then we remove $$$a_2 = 2$$$, so the score becomes $$$5$$$, and the array becomes $$$[1, 4]$$$. Finally, we remove $$$a_2 = 4$$$, and the score becomes $$$9$$$. Now the length of the array is less than $$$k=2$$$, so no more operations can be performed. It can be proven that the maximum score is $$$9$$$.

In the second test case, we can only perform one operation, either removing $$$a_1 = 3$$$ or $$$a_4 = 2$$$. Obviously, it is better to remove $$$a_1 = 3$$$ to get a score of $$$3$$$.