You work in a national agency. And the boss assigned you as the fire coordinator. In a fire alarm, you have to coordinate the evacuation of all people from the building safely. For this purpose, you are also preparing the list for "items to be removed first".

In the list, every item is recorded with its weight and price (or importance factor). Because, you have limited capacity and you cannot take everything at once, you start with the item which has the most importance factor per unit weight. The items are important and you cannot break them into pieces, so either you take an item or you don't take it. It's an emergency case, and you can get at most k kgs.

Question: The list automatically updated by the staff and in a fire alarm you will print this list and follow the procedures :) Write a program that will calculate at most how much importance factor you can safely save.

Input specification
You will be given two integers in the beginning: the number of items (n) and total weight (k) you can carry where 1 ≤ n ≤1,000 and 1 ≤ k ≤ 400. Then the following n lines will contain 3 integers

• Item ID: an integer between 1 and 10,000.
• Item weight: an integer between 4 and 200.
• Importance factor or price: an integer between 1 and 500.

Output specification
Show one integer total importance (price) that you can safely evacuate.

Explanation: You have four items and you can carry at most 16 kgs. If you take Item 1 and Item 2, you can save totally 15 kgs and $119 (or 119 importance factor).