该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

WDJ 做梦来到《雪魔（SIMO）世界》里，刀哥说：“想要 5 倍积分？那就来挑战这些难题吧！” 每道题的挑战结果与请教老师的次数相关，WDJ 需合理安排请教次数，以获取最高积分！

题目描述

WDJ 面前有 $n$ 道难题排成一排，他手中有 $x$ 次 “请教老师的机会”（每次请教消耗 1 次机会，可累积使用）。

• 对第 $i$ 道题：
  • 失败 可获得 ${\rm lose}_i$ 积分（无论是否请教，只要未满足最低请教次数即失败）；
  • 胜利 可获得 ${\rm win}_i$ 积分（需一次性使用至少 ${\rm use}_i$ 次请教机会，不足则失败）；
  • 注意：若选择使用 $k$ 次请教机会挑战第 $i$ 题，当 $k < {\rm use}_i$ 时必败，且 $k$ 次机会浪费。

目标：合理分配请教次数，最大化积分总和 $s$，最终输出 $5 \times s$。

输入格式

第一行包含两个整数 $n$ 和 $x$（$0 \leq n, x \leq 10^3$），分别表示题目数和总请教次数。 接下来 $n$ 行，每行三个整数 ${\rm lose}_i$、${\rm win}_i$、${\rm use}_i$（$0 < {\rm lose}_i \leq {\rm win}_i \leq 10^6$，$0 \leq {\rm use}_i \leq 10^3$），依次表示每道题失败积分、胜利积分、最低请教次数。

输出格式

一个整数，表示最大积分总和的 5 倍。

样例输入

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

样例输出

1060

样例解释

选择部分题目胜利、部分失败，最优积分为 $212$（例如：胜利第 1、3、5、6 题，失败第 2、4 题），最终输出 $212 \times 5 = 1060$。

数据范围与提示

• 10% 数据：$x = 0$（只能全部失败）。
• 30% 数据：$0 \leq n \leq 10$，$0 \leq x \leq 20$。
• 60% 数据：$0 \leq n, x \leq 100$，$10 < {\rm lose}_i, {\rm win}_i \leq 100$，$0 \leq {\rm use}_i \leq 5$。
• 100% 数据：$0 \leq n, x \leq 10^3$，$0 < {\rm lose}_i \leq {\rm win}_i \leq 10^6$，$0 \leq {\rm use}_i \leq 10^3$。