3510: CRB and His Birthday HDU - 5410
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：4
Solved：3
Description
Today is CRB's birthday. His mom decided to buy many presents for her lovely son.
She went to the nearest shop with MM Won(currency unit).
At the shop, there are NN kinds of presents.
It costs W_{i}Wi Won to buy one present of ii-th kind. (So it costs kk × W_{i}Wi Won to buy kk of them.)
But as the counter of the shop is her friend, the counter will give A_{i}\ ×\ x\ +\ B_{i}Ai × x + Bi candies if she buys xx(xx>0) presents of ii-th kind.
She wants to receive maximum candies. Your task is to help her.
1 ≤ TT ≤ 20
1 ≤ MM ≤ 2000
1 ≤ NN ≤ 1000
0 ≤ A_{i},\ B_{i}Ai, Bi ≤ 2000
1 ≤ W_{i}Wi ≤ 2000
She went to the nearest shop with MM Won(currency unit).
At the shop, there are NN kinds of presents.
It costs W_{i}Wi Won to buy one present of ii-th kind. (So it costs kk × W_{i}Wi Won to buy kk of them.)
But as the counter of the shop is her friend, the counter will give A_{i}\ ×\ x\ +\ B_{i}Ai × x + Bi candies if she buys xx(xx>0) presents of ii-th kind.
She wants to receive maximum candies. Your task is to help her.
1 ≤ TT ≤ 20
1 ≤ MM ≤ 2000
1 ≤ NN ≤ 1000
0 ≤ A_{i},\ B_{i}Ai, Bi ≤ 2000
1 ≤ W_{i}Wi ≤ 2000
Input
There are multiple test cases. The first line of input contains an integer TT, indicating the number of test cases. For each test case:
The first line contains two integers MM and NN.
Then NN lines follow, ii-th line contains three space separated integers W_{i}Wi, A_{i}Ai and B_{i}Bi.
The first line contains two integers MM and NN.
Then NN lines follow, ii-th line contains three space separated integers W_{i}Wi, A_{i}Ai and B_{i}Bi.
Output
For each test case, output the maximum candies she can gain.
Sample Input Copy
1
100 2
10 2 1
20 1 1Sample Output Copy
21HINT
CRB's mom buys 10 presents of first kind, and receives 2 × 10 + 1 = 21 candies.