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 \(V_i\) VNĐ, weighs \(W_i\) kilograms, and there are \(K_i\) 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?

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 \(V_i\), \(W_i\) and \(K_i\), the value in VNĐ, weight in kilograms and number of the \(i\)-th item respectively. 

Output:

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

Limit:

\(1 \leq S \leq 2000\); \(1 \leq V_i \leq 1000000\); \(1 \leq W_i \leq S\); \(1 \leq N \leq 100000\); \(1 \leq Ki \leq 10^9\)