A学校的食堂来市场上采购粮食，他们准备了n元，市场上有m种不同的粮食，每种粮食都是袋装的，只能整袋购买；不同种类的粮食价格、重量、袋数有差异（也可能相同，比如：大米和小米，可以是同一个重量的包装）。
请问：食堂以有限的资金，最多能购买到多少公斤的粮食。
本题有多组测试数据，第1行读入一个整数t代表测试数据的组数。（t≤10）
对于每组测试数据，先读入两个整数n和m。(1≤n≤100, 1≤m≤100)
接下来m行，每行有3个整数 x , y , z ，分别代表每种粮食的价格、重量、袋数。(1≤x≤20,1≤y≤200,1≤z≤20)
对于每组测试数据，请输出能够购买粮食的最多重量，食堂准备的经费可能买不光所有的大米，经费可以不用完。每组输出占一行。
1 42 6 10 1 15 19 79 5 6 65 3 8 82 6 16 92 2 17 28 3
441