Description

A traveler has a backpack that can hold at most $V$ kilograms. There are $n$ items available, with weights $W_1$, $W_2$, ..., $W_n$ and values $C_1$, $C_2$, ..., $C_n$. Some items can only be taken once (0-1 knapsack), some can be taken unlimited times (unbounded knapsack), and some have a maximum number of times they can be taken (bounded knapsack). Find which items to put in the backpack so that the total weight does not exceed the backpack capacity and the total value is maximized.

Input Format

The first line contains two integers: $M$ (backpack capacity, $M ≤ 200$) and $N$ (number of items, $N ≤ 30$).
Lines $2$ to $N+1$ each contain three integers $W_i$, $C_i$, and $P_i$. The first two integers represent the weight and value of each item. The third integer $P_i$ indicates the type of item: if it is $0$, the item can be taken unlimited times; otherwise, it represents the maximum number of times the item can be taken.

Output Format

A single line containing one number, representing the maximum total value.

Sample

10  3
2  1  0
3  3  1
4  5  4

11