Mixed Knapsack

Background

Special for beginners, ^_^

Problem Description

A traveler has a knapsack that can hold at most $V$ kilograms. Now there are $n$ items with weights $W_1, W_2, \dots, W_n$ and values $C_1, C_2, \dots, C_n$. Some items can be taken only once (0/1 knapsack), some can be taken an unlimited number of times (unbounded knapsack), and some can be taken at most a limited number of times (bounded knapsack). Solve which items to put into the knapsack so that the total cost does not exceed the knapsack capacity and the total value is maximized.

Input Format

The first line has two integers, $M$ (knapsack capacity, $M \le 200$) and $N$ (number of items, $N \le 30$).

Lines $2 \dots N+1$: line $i$ has three integers $W_i, C_i, P_i$. The first two integers are the weight and value of each item. If the third integer is $0$, the item can be taken any number of times; otherwise it is the maximum number $P_i$ of copies that can be taken.

Output Format

A single line with one number: the maximum total value.

Sample Input 1

10 3
2 1 0
3 3 1
4 5 4

Sample Output 1

11

Constraints

1s, 1024KiB for each test case.

Take $1$ copy of the first item and $2$ copies of the third item.