Description

SQK上山去采药。SQK有一个容量为$m(1 \leq m \leq 1000)$的背包，他所采集的药材的总重量不能大于背包的容量。已知共有$n(1 \leq n \leq 100 )$种药材，每种药材都有自己的价值，并且知道每种药材的数量是有限的，如何选择，才能使得背包中药材价值最大？

Input

输入数据首先包含一个正整数$C(1 \leq C \leq 10)$，表示有C组测试用例，每组测试用例的第一行是两个整数$m$和$n(1 \leq m \leq 1000, 1 \leq n \leq 100)$,分别表背包的负重和药材的种类，然后是$n$行数据，每行包含$3$个数$w，v和c(1 \leq w \leq 100,1 \leq v \leq 200,1 \leq c \leq 100)$，分别表示每种药材的重量、每株的价值以及对应种类药材的株数。

Output

对于每组测试数据，请输出能够采集药材的最大价值，每个实例的输出占一行。

Sample Input

1
8 2
2 100 4
4 100 2

Sample Output

400