Description

A traveler has a backpack that can hold a maximum of V kilograms. There are now n items, with their weights being $W\_1, W\_2, ..., W\_n$ and their values being $C\_1, C\_2, ..., C\_n$. Some items can only be taken once (01 knapsack), some can be taken an unlimited number of times (unbounded knapsack), and some have an upper limit on the number of times they can be taken (bounded knapsack). The goal is to determine which items to pack into the backpack so that the total weight does not exceed the backpack's capacity and the total value is maximized.

Input Format

First line: Two integers, M (backpack capacity, M ≤ 200) and N (number of items, N ≤ 30);
Lines 2 to N+1: Each line contains three integers $W\_i, C\_i, P\_i$. The first two integers represent the weight and value of each item, respectively. The third integer, if 0, indicates that the item can be purchased an unlimited number of times; if it is another number, it represents the maximum number of times the item can be purchased ($P\_i$).

Output Format

A single line containing a number, which represents the maximum total value.

10  3
2  1  0
3  3  1
4  5  4

11

Hint

Select 1 piece of the first item and 2 pieces of the third item.