题目描述

小华参加了一个限时挑战活动，每击败一名对手可以获得五倍经验。他准备了 $x$ 个迷你装药物（每个只能使用一次），需要决定对哪些对手使用药物来击败他们，哪些对手直接认输。

对于每个对手，如果使用药物击败他，需要消耗一定数量的药物并获得胜利经验；如果认输，则不消耗药物但只能获得较少的失败经验。如果药物数量不足以击败该对手，则击败失败且药物仍然消耗。

现在有 $n$ 个对手，给定失败时可获得的经验、胜利时可获得的经验，以及击败他至少需要的药量。要求求出最大经验 $s$，输出 $5s$。

输入格式

第一行两个数，$n$ 和 $x$。

后面 $n$ 行每行三个数，分别表示失败时获得的经验 $\mathit{lose}_i$，胜利时获得的经验 $\mathit{win}_i$ 和打过要至少使用的药数量 $\mathit{use}_i$。

输出格式

一个整数，最多获得的经验的五倍。

样例

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

1060

提示

【数据范围】

• 对于 $10\%$ 的数据，保证 $x = 0$。
• 对于 $30\%$ 的数据，保证 $0 \le n \le 10$，$0 \le x \le 20$。
• 对于 $60\%$ 的数据，保证 $0 \le n, x \le 100$，$10 \lt \mathit{lose}_i, \mathit{win}_i \le 100$，$0 \le \mathit{use}_i \le 5$。
• 对于 $100\%$ 的数据，保证 $0 \le n, x \le 10^3$，$0 \lt \mathit{lose}_i \le \mathit{win}_i \le 10^6$，$0 \le \mathit{use}_i \le 10^3$。