Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

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

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}$.

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}$.

提交代码