某个人保存了许多视频，但他的的硬盘不够大。所以他不得不把它们转刻到光盘上保存。于是他想尽可能地利用好光盘的每一bit空间，尽可能把光盘刻得满满的。
现在他手头上拿到了一张空白容量为S MB的光盘，他文件夹里有N个电影，每个电影的大小分别为X1、X2、……、XN，单位为MB。
请你帮他编写一个程序，计算到底光盘最大能刻得多满，单位为MB。


Input



第一个数字为T，表示测试数据的组数，T≤10。
接下来的T行的每行第一个数字为1≤S≤10000，表示光盘的空白容量，第二个数字1≤N≤10000，表示电影的个数，随后的N个整数X1、X2、……、XN表示每个电影的大小（1≤X≤10000）。





Output



共T行，每一行包含一个整数，表示该光盘能刻录的最大容量。



Sample Input



3
4000 3 100 200 300
450 3 100 200 300
100 3 200 300 400



Sample Output



600
400
0

背包问题，贪心法求解。