Russell loves solving math problems and also playing online games. Recently, he has started playing a game called BAPG. At the beginning of the game you are given limited bullets n and there are m enemies to kill. As Russell is a pro BAPG player, he spends only one bullet to kill an enemy. Killing each enemy gives bonus points which he can use to purchase in game elements. Bonus points for killing 1st,2nd….m’th enemies are a1, a2, ..., am. If Russell kills enemies optimally can you tell the maximum point he can get after spending all n bullets.

Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T (1 <= T <= 100) test cases follows. First line of each test case contains two integers n and m(1 <= n,m <= 1000), the number of bullets and numbers of enemies. Second line contains m space-separated integers a1, a2, ..., am(1 <= ai <= 1012), the bonus points.

Output

For each test case, print a single line containing one integer, the maximum points Russell can get.