家里现在没米了，老周让小周周去买米。

第一行包含一个正整数 $C\ (C \leq 100)$，表示有 $C$ 组测试用例。
每组测试用例的第一行是两个整数 $n,\ m,\ (1 \leq n \leq 100,\ 1 \leq m \leq 100)$，分别表示经费的金额和大米的种类。
然后是 $m$ 行数据，每行包含 $3$ 个数 $p,\ h,\ c,\ (1 \leq p \leq 20,\ 1 \leq h \leq 200,\ 1 \leq c \leq 20)$，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。

对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。