CRB and His Birthday

Today is CRB's birthday. His mom decided to buy many presents for her lovely son.
She went to the nearest shop with $M$ Won(currency unit).
At the shop, there are $N$ kinds of presents.
It costs $W_{i}$ Won to buy one present of $i$-th kind. (So it costs $k$ × $W_{i}$ Won to buy $k$ of them.)
But as the counter of the shop is her friend, the counter will give $A_{i}\ ×\ x\ +\ B_{i}$ candies if she buys $x$($x$>0) presents of $i$-th kind.
She wants to receive maximum candies. Your task is to help her.
1 ≤ $T$ ≤ 20
1 ≤ $M$ ≤ 2000
1 ≤ $N$ ≤ 1000
0 ≤ $A_{i},\ B_{i}$ ≤ 2000
1 ≤ $W_{i}$ ≤ 2000

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains two integers $M$ and $N$.
Then $N$ lines follow, $i$-th line contains three space separated integers $W_{i}$, $A_{i}$ and $B_{i}$.

For each test case, output the maximum candies she can gain.

1
100 2
10 2 1
20 1 1

21

CRB's mom buys 10 presents of first kind, and receives 2 × 10 + 1 = 21 candies.

KUT（DPRK）

2015 Multi-University Training Contest 10