Bounded Knapsack Problem

There are N types of items and a knapsack with capacity V.

Each item of type i has a maximum availability of s_i units. Each unit of type i has a volume of v_i and a value of w_i.

Determine which items to put into the knapsack such that the total volume does not exceed the capacity and the total value is maximized. Output the maximum value.

Input Format

The first line contains two integers, N and V (0 < N ≤ 1000, 0 < V ≤ 20000), separated by a space, representing the number of item types and the knapsack capacity respectively.

The next N lines each contain three integers v_i, w_i, s_i, separated by spaces, representing the volume, value, and maximum quantity for the i-th type of item.

Output Format

Output a single integer, representing the maximum value.

Constraints

0 < N ≤ 1000

0 < V ≤ 20000

0 < v_i, w_i, s_i ≤ 20000

Note

This problem tests the monotonic queue optimization method for the Bounded Knapsack problem.

Sample Input

4 5
1 2 3
2 4 1
3 4 3
4 5 2

Sample Output

10