Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
 Register new ID

K Subsequence

Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 4320    Accepted Submission(s): 1089

Problem Description
Master QWsin is dating with Sindar. And now they are in a restaurant, the restaurant has $n$ dishes in order. For each dish, it has a delicious value $ai$. However, they can only order $k$ 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 $subsequence$ of dishes and in this $subsequence$, when $i < j$, the subsequence must satisfies $ai \leq aj$. After a round, they will get the sum of the $subsequence$ 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?

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

First line contains two positive integers $n$ and $k$ which are separated by spaces.

Second line contains $n$ positive integer $a1$,$a2$,$a3$...$an$ represent the delicious value of each dish.

$1 \leq T \leq 5$

$1 \leq n \leq 2000$

$1 \leq k \leq 10$

$1 \leq ai \leq 1e5$

Only an integer represent the maximum happiness value they can get.

Sample Input
1 9 2 5 3 2 1 4 2 1 4 6

Sample Output


Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-06-17 02:13:29, Gzip enabled