Problem P: Evil Peggy

Problem P: Evil Peggy

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 24  Solved: 4
[Submit][Status][Web Board]

Description

Peggy is a lovely girl. One day, she brought n toys to her classroom. The toys are so cute that her K classmates want to borrow them to play. Every toy has a index i(\(1 <= i <= n\)) and every student wants to get a continuous indexes of toys. Every toy also has a happy value \(a_i\). The happy value can be 0 or even smaller which means the toy makes someone unhappy. The happy value of each student is defined as the sum of the happy values of all the toys he/she borrows. But Peggy is evil, so she doesn't want her classmates to be too happy. She wants to minimize the maximum happy value of her K classmates. She can hide some last indexed toys and not distribute them, which means she can just split the first x(\(k<=x<=n\)) toys into k parts and throws away the rest. Each part of one classmate chooses is consecutive and no two parts intersect. Also, every classmate must get at least one toy. Now she asks you the smallest value of the maximum happy value of the K classmates.

\(1<=T<=10\)
\(1<=k<=n<=2*10^5\)
\(-10^9<=a_i<=10^9\)

Input

Input contains multiple test cases.

The first line of the input is a single integer T which is the number of test cases. T test cases follow.

Each test case contains two lines.

For each test case, the first line contains two integer n, k. The second line contains n integers a1 ,a2,…, an−1,an

And it satisfies thatn<=2*10^5.

Output


For each case, print the smallest maximum happy value of the K classmates, and one line one case.

Sample Input

2
4 2
3 -2  4 -2
5 4
-1 -1 -1 -1 6

Sample Output

2
-1

HINT

[Submit][Status]