You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

In the kingdom of Algoria, a wizard named Thales needs to gather a collection of magical treasures to aid in his journey. He is given an array A[] with N length. This array of magical values represents treasures, and he must select a contiguous subarray of length K such that the total magical value is as small as possible. Before making his selection, he is allowed to swap the positions of any two treasures at most once to improve the total value of his chosen subarray.

Your task is to help Thales find the minimum possible sum of magical values by selecting a contiguous subarray of length K, either with or without a swap.

Input

• First line T,(1 ≤ T ≤ 10000) number of test cases.
• In each test case, first line two positive integers N, (1 ≤ N ≤ 100000) and K, (1 ≤ K ≤ N).
• Second line an array A[],(\(-10^5<=A[]<=10^5\)) with N length.

Sum of N overall test cases doesn't exceed \(2 * 10^5\)

Output

In each test case, print the minimum possible sum of magical values.

Sample

3
4 3
-6 3 9 -4 
3 2
7 -9 8 
4 2
0 -1 0 -9 

-7
-2
-10

First test case :
Initially array A[] = {-6, 3, 9, -4 }.
We can select index 3 and 4 and swap their value.
After swap, array A[] = {-6, 3, -4, 9}.
Now we can select K=3, length subaray from 1 to 3, [-6,3,-4].
Total sum of this subarray is -7, which is minimum.