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\)