Minimum Cost for Chocolate Consumption

Little Blue loves chocolate and eats one chocolate every day. One day, he visits a supermarket where many types of chocolates are available. Each type of chocolate has its own price, available quantity, and remaining shelf life (the number of days left before it expires). A chocolate with a remaining shelf life of d can only be consumed on one of the first d days.

Given n types of chocolates and an integer x representing the number of consecutive days Little Blue wants to eat chocolate, determine the minimum total cost required to purchase x chocolates so that he can consume one chocolate per day without eating an expired one. If it is impossible to cover all x days under these constraints, output -1.

The problem can be formulated as follows:

For each chocolate type, you are given its price p, available quantity q, and expiration day d. When planning to eat chocolate for x days, we must assign each day (from day 1 to day x) a chocolate such that if a chocolate is used for day i, then its remaining shelf life d satisfies i ≤ d. The goal is to minimize the sum of prices for the selected chocolates.

Hint: A dynamic programming solution can be used. Let dp[i] represent the minimum cost to cover i days. For each chocolate type with parameters (p, q, d), try purchasing between 0 and q chocolates to cover additional days. However, note that if you already planned for j days, then you can only add at most (d - j) chocolates from this type (since the chocolate can only be used on days ≤ d). Update the DP table accordingly.

inputFormat

The first line contains two integers n and x, where n is the number of chocolate types and x is the number of days Little Blue wants to eat chocolate.

Each of the next n lines contains three integers p, q, and d:

• p – the price of one chocolate of that type;
• q – the quantity available of that type;
• d – the number of days remaining before expiration. A chocolate with expiration d can be consumed only on days 1 through d (inclusive).

outputFormat

Output a single integer representing the minimum total cost to purchase x chocolates so that Little Blue can eat one chocolate per day without consuming an expired chocolate. If it is impossible to cover all x days, output -1.

sample

3 5
1 3 3
2 4 6
3 2 5

7