Maximize Experience with Limited Mini Drugs

Absi2011 has $x$ mini-drugs, each of which can be used only once. He is preparing to fight $n$ friends. For each friend, two experience values are given: the experience obtained when you lose and the experience obtained when you win. To win against a friend, you must use at least a specified number of drugs. If you use a number of drugs less than the required amount, you lose and the drugs you used are wasted.

More formally, for each friend you have three parameters:

• fail_exp: the experience you gain if you lose (by using fewer than $r$ drugs).
• win_exp: the experience you gain if you win (by using at least $r$ drugs).
• $r$: the minimum number of drugs needed to win against that friend.

You must fight all $n$ friends in order. For each friend, you have two choices:

1. Sacrifice no drugs and lose, receiving fail_exp while keeping your drugs intact.
2. Invest exactly $r$ drugs to win (if you have enough drugs remaining), receiving win_exp. Note that if win_exp is not greater than fail_exp, it is never beneficial to invest drugs.

Your goal is to maximize the total experience $s$ earned from the battles. Finally, you must output $5s$.

Hint: The baseline experience is the sum of fail_exp for all friends, and using drugs to win gives you an extra profit of win_exp - fail_exp at a cost of $r$ drugs. This can be solved using a 0-1 knapsack approach.

inputFormat

The first line contains two integers n and x (1 ≤ n, x ≤ 10^4), where n is the number of friends and x is the total number of mini-drugs available.

Each of the following n lines contains three integers: fail_exp, win_exp and r (0 ≤ fail_exp, win_exp ≤ 10^4 and 1 ≤ r ≤ x), representing the experience gained on losing, the experience gained on winning, and the minimum number of drugs required to win against that friend, respectively.

outputFormat

Output a single integer, which is 5s, where s is the maximum total experience you can achieve by carefully using your mini-drugs.

sample

3 5
10 20 3
5 6 2
8 8 4

170