Master QWsin is dating with Sindar. And now they are in a restaurant, the restaurant has nn dishes in order. For each dish, it has a delicious value aiai. However, they can only order kk times. QWsin and Sindar have a special ordering method, because they believe that by this way they can get maximum happiness value.
Specifically, for each order, they will choose a subsequencesubsequence of dishes and in this subsequencesubsequence, when i<ji<j, the subsequence must satisfies ai≤ajai≤aj. After a round, they will get the sum of the subsequencesubsequence and they can't choose these dishes again.
Now, master QWsin wants to know the maximum happiness value they can get but he thinks it's too easy, so he gives the problem to you. Can you answer his question?
Input
There are multiple test cases. The first line of the input contains an integer TT, indicating the number of test cases. For each test case:
First line contains two positive integers nn and kk which are separated by spaces.
Second line contains nn positive integer a1a1,a2a2,a3a3...anan represent the delicious value of each dish.
1≤T≤51≤T≤5
1≤n≤20001≤n≤2000
1≤k≤101≤k≤10
1≤ai≤1e51≤ai≤1e5
Output
Only an integer represent the maximum happiness value they can get.