Description

Now absi2011 has taken out $x$ mini attribute potions (taking potions to fight is shameful...), and is ready to fight those people.

Since each mini attribute potion can only be used once, absi2011 must use them carefully. Unfortunately, if the amount of potions used does not reach the minimum required to defeat someone, then that fight is a guaranteed loss. For example, if he uses $2$ potions to fight someone, but it actually takes $3$ potions to win, then you lose, and those two attribute potions are wasted.

There are $n$ friends. For each, you are given the experience for losing, the experience for winning, and the minimum number of potions required to defeat that friend.

Find the maximum experience $s$, and output $5s$.

Input Format

The first line contains two integers, $n$ and $x$.

Each of the next $n$ lines contains three integers, representing the experience gained on a loss $\mathit{lose}_i$, the experience gained on a win $\mathit{win}_i$, and the minimum number of potions required to defeat that friend $\mathit{use}_i$.

Output Format

A single integer, which is five times the maximum obtainable experience.

6 8
21 52 1
21 70 5
21 48 2
14 38 3
14 36 1
14 36 2

1060

Hint

• Hint: During the 5x experience event, absi2011 always uses stamina potions instead of these attribute potions.

• Constraints:

  • For $10\%$ of the testdata, it is guaranteed that $x = 0$.
  • For $30\%$ of the testdata, it is guaranteed that $0 \le n \le 10$, $0 \le x \le 20$.
  • For $60\%$ of the testdata, it is guaranteed that $0 \le n, x \le 100$, $10 < \mathit{lose}_i, \mathit{win}_i \le 100$, $0 \le \mathit{use}_i \le 5$.
  • For $100\%$ of the testdata, it is guaranteed that $0 \le n, x \le 10^3$, $0 < \mathit{lose}_i \le \mathit{win}_i \le 10^6$, $0 \le \mathit{use}_i \le 10^3$.

• Problem Source: fight.pet.qq.com. Authorized by absi2011.

Translated by ChatGPT 5