Knapsack

There is a housewife who recently won a prize to “shop for free as long as your shopping basket is not full” in a department store.

This housewife is given a shopping basket that can carry a maximal weight of S kilograms.

There are N item types in the department store and the i-th item is worth Vi SGD, weighs Wi kilograms, and there are Ki copies (of exactly same value and weight) of such item i.

For example, there are N = 3 item types: meat, milk, and bread; of which there are: 1 pack of meat, 3 bottles of milk, and 4 loaves of bread (see the last sample test case).

What items should the housewife take to maximize the total value of the items in her shopping basket?

Your program must read from standard input.

The first line of input contains two positive integers, S and N.

The next N lines of input will each contain three integers, where the i-th line contains Vi, Wi and Ki, the value in SGD, weight in kilograms and number of the i-th item respectively.

Your program must print to standard output.

Your program should print one integer, representing the maximum total value in SGD of the items that this housewife can take while ensuring the total weight does not exceed S kilograms.

• 1 ≤ S ≤ 2000
• 1 ≤ Vi ≤ 1000000
• 1 ≤ Wi ≤ S
• 1 ≤ N ≤ 100000
• 1 ≤ Ki ≤ 109