题目描述

Dr Lu says we need to have more easy problems so that every one attending the contest can solve them. Though the problem above is easy enough, he also wants some more easy problems, so this problem is set.

As the title of the problem indicates, this is also a check in problem, but we have made one above, so this problem may be harder than the problem Check in I.

Suppose we are in the canteen of QLU. There are many tables we can get foods, and for every table, there are many promotion strategies to sell the food well, which we can think that all the strategies are like: Buy $x$ piece of food then give $y$ additional piece of food as gifts.

For example, suppose the strategy for some table is Buy $3$ piece of food then give $1$ additional piece of food as a gift, which means if you buy $3$ piece of food then you can get $1$ piece of food for free.

Now you have $n$ yuan, please calculate the maximum number of food you can get.

It is guaranteed that every table can afford your purchases.

输入格式

The first line of the input contains two positive integers $n,m$ which indicates that now you have $n$ yuan and there are $m$ tables in the canteen$(1\le n,m\le100)$.

Then followed $m$ lines each line contains the description of the table which contains three positive integers $x_i,y_i,z_i$ indicating the cost of one piece of food and the strategy: Buy $y_i$ piece of food then give $z_i$ additional piece of food as gifts.

It is guaranteed that for each $1\le x_i \le n$ and $1\le z_i \le y_i \le 100$

输出格式

The maximum number of food you can get.

样例

5 3 
1 3 2 
4 2 1 
5 1 1

7

提示

For the test case, we can buy the food in the first table, so we can get 7 piece of food.