Subprojects

Ramzi Sarnayeh has founded a new suburban services company named Undetermined Ideas (UI). Since UI is young, Ramzi has not hired employees yet. Therefore he’s alone in first few months and must manage everything himself sequentially until he can extend his work. Recently he has acquired some projects from government ministries and has broken all projects to small independent subprojects with different values. We can assume all subprojects can be accomplished in one time unit. Unfortunately, Ramzi has limited available time and being optimistic, he wants to know how much, at best, he can earn by accepting valuable subprojects and rejecting the others.

Specifications

Input

The first line of input contains an integer, the number of test cases. Following, there is one line for each test case. Each test case begins with two integers that are Ramzi’s available time (T) and the number of subprojects (P), respectively (0 ≤ T, P ≤ 1000). Following these two numbers, there are P non-negative integers (between 0 and 32767, inclusively) which are values of subprojects. All numbers in test cases are separated by one blank character.

Output

There should be one line for each test case in output. Each line should contain one integer number which is the maximum earning (sum of values) that can be achieved within Ramzi’s available time.

Problem information

Time Limit: 1 seconds
Memory Limit: 64 MB
Balls for the passed test: 10
Complexity: 10% 203/225
My result: 0/1

Example

Example input

3
3 5 1 1 1 1 1
4 2 161 5
4 7 8 2 9 17 4 4 10

Example output

3
166
44

← A Piece of Paper

Problems

Truck Driving →