问题描述

今天是CRB的生日。他的妈妈决定为她可爱的儿子买很多礼物。
她带着M韩元（货币单位）去了最近的商店。
商店里有N种礼物。
买第i种礼物一件需要Wi韩元。（所以买k件需要k × Wi韩元。）
但由于商店柜台是她的朋友，如果她买x件第i种礼物（x>0），柜台会给她Ai × x + Bi颗糖果。
她想要获得最多的糖果。你的任务是帮助她。
1 ≤ T ≤ 20
1 ≤ M ≤ 2000
1 ≤ N ≤ 1000
0 ≤ Ai, Bi ≤ 2000
1 ≤ Wi ≤ 2000

输入

有多组测试用例。输入的第一行包含一个整数T，表示测试用例的数量。对于每个测试用例：
第一行包含两个整数M和N。
接下来N行，第i行包含三个用空格分隔的整数Wi, Ai和Bi。

输出

对于每个测试用例，输出她能获得的最大糖果数。

1
100 2
10 2 1
20 1 1

21

提示

CRB的妈妈买了10件第一种礼物，收到2 × 10 + 1 = 21颗糖果。