Free Shopping Knapsack

You have obtained a "free shopping" coupon from a supermarket. You are given a shopping basket with capacity \(S\), and there are \(n\) different types of items in the store. For the \(i\)-th item, its weight is \(w_i\), its value is \(v_i\), and there are \(k_i\) copies available.

You can fill your basket with any items you want as long as the total weight does not exceed the basket's capacity \(S\). Your task is to determine the maximum total value of items you can take home under these conditions.

Note: Do not underestimate the difficulty of this problem. Please check the data size section if you intended to write a naive solution.

inputFormat

The first line contains two integers (n) and (S) separated by a space, representing the number of item types and the capacity of the basket respectively. This is followed by (n) lines, each containing three integers (w_i), (v_i), and (k_i), which denote the weight, value, and available quantity of the (i)-th item.

outputFormat

Output a single integer, the maximum total value of items that can be put into the basket without exceeding the capacity.

sample

3 10
3 4 2
4 5 1
2 3 3

14