问题描述

在某颗星球上，正在进行一场名为“来自DWANGO的挑战状”的编程竞赛预选赛，预选赛的通过者将被邀请前往决赛场地。

这颗星球上有一条长度为$L$的环形线路，上面有$N$个城市。每个城市都有一个从1到N的编号，以$1$号城市为基准，按顺时针的方式编号。

决赛可以在一个或多个城市进行，并决定每个比赛场地进行现场直播。

每个城市和每个比赛场地都确定了参与决赛的居民数量和进入比赛场地的选手人数。

进入比赛场地的总选手人数与参与决赛的总选手人数完全相等。

有些城市的居住选手人数与进入比赛场地的选手人数可能不相等，这种情况下需要通过出租车将决赛选手从一个城市移动到另一个城市。

出租车可以沿着环形线路移动，每个决赛选手的移动距离将产生相应的移动成本。

请编写一个程序，找出所有可能的移动成本的最小值。

输入

输入数据以以下格式从标准输入中给出。

$N$ $L$ $a_1$ $b_1$ $c_1$ $a_2$ $b_2$ $c_2$ : $a_N$ $b_N$ $c_N$

• 第一行为城市数量$N (2 ≤ N ≤ 100,000)$和环形线路长度$L (N ≤ L ≤ 10,000,000)$，以空格分隔。
• 第二行到第$N$行给出与每个城市相关的信息。其中第$i (1 ≤ i ≤ N)$行包含三个整数$a_i (0 ≤ a_i ≤ L - 1)$，$b_i (0 ≤ b_i ≤ 100,000)$，$c_i (0 ≤ c_i ≤ 100,000)$，以空格分隔。这表示城市$i$位于沿着环形线路，从基准城市1开始逆时针前进$a_i$的位置，城市$i$有$b_i$名参赛选手，如果$c_i = 0$，则城市$i$没有比赛场地，如果$c_i > 0$，则城市$i$邀请$c_i$名选手参加决赛。
• $a_1 = 0$，且对于所有整数$i (2 ≤ i ≤ N)$，有$a_i > a_{i-1}$成立。
• $b_1 + ... + b_N = c_1 + ... + c_N$。
• $b_1 + ... + b_N ≥ 1$。

部分评分

此问题有部分得分。

• 如果满足$N ≤ 5,000$且$b_1 + ... + b_N ≤ 5,000$的数据集$1$全部正确，则得到$15$分。
• 如果满足$N ≤ 5,000$的数据集$2$全部正确，则额外获得$30$分。
• 如果满足没有额外约束的数据集$3$全部正确，则额外获得$55$分，总分为$100$分。

输出

输出移动成本的最小值，输出占一行。末尾加上换行符。

输入示例1

7 30
0 3 6
1 2 2
4 5 4
19 0 1
20 4 4
21 1 0
27 3 1

输出示例1

12

考虑以下移动：

• 城市3的1名决赛选手通过出租车逆时针移动到城市1。移动成本为$4 × 1 = 4$。
• 城市6的1名决赛选手通过出租车逆时针移动到城市4。移动成本为$2 × 1 = 2$。
• 城市7的2名决赛选手通过出租车顺时针移动到城市1。移动成本为2名选手共$3 × 2 = 6$。

由于这些移动产生的结果是无论移动后的城市是否存在比赛场地，该城市的参与决赛选手数量与进入比赛场地的选手数量相等，并且所有决赛选手都能进入比赛场地。

移动成本的总值为$4 + 2 + 6 = 12$，这个值为最小值。

输入示例2

6 25
0 10 1
3 0 1
9 0 2
12 0 3
13 0 2
21 0 1

输出示例2

85