AT_dwango2015_prelims_4 タクシー

在某个星球上进行了一场编程竞赛的预选赛，名为「ドワンゴからの挑戦状」，预选赛的合格者将被邀请参加正赛。 这个星球上有一条长度为 $ 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 \leq N \leq 100,000) $ 和 $ L\ (N \leq L \leq 10,000,000) $，分别代表城市数量和环形道路的长度。 - 接下来的 $ N $ 行，每行包括三个整数 $ a_i\ (0 \leq a_i \leq L - 1) $, $ b_i\ (0 \leq b_i \leq 100,000) $, $ c_i\ (0 \leq c_i \leq 100,000) $，分别表示第 $ i $ 个城市的相对位置，出发参赛者数量，以及该城市如果有会场可以接待的参赛者数量。 - $ a_1 = 0 $ 表示城市 $ 1 $ 的起始位置，$ a_i > a_{i-1} $ 对于所有 $ i\ (2 \leq i \leq N) $ 都成立。 - $ b_1 + \dots + b_N = c_1 + \dots + c_N $。 - $ b_1 + \dots + b_N \geq 1 $。

输出一行，表示可能的最小运输成本。确保输出行末有换行符。

### 部分评分 该题目有部分评分。根据不同的数据集限制，可以得到不同的分数： - 约束 $ N \leq 5,000 $ 且 $ b_1 + \dots + b_N \leq 5,000 $ 的数据集 1，正确解答可得到 15 分。 - 约束 $ N \leq 5,000 $ 的数据集 2，正确解答可得到额外 30 分。 - 无额外限制的数据集 3，正确解答可得到额外 55 分，总计 100 分。 ### 样例解释 1 考虑以下移动方案： - 城市 $ 3 $ 的一名参赛者逆时针移动到城市 $ 1 $。移动成本为 $ 4 \times 1 = 4 $。 - 城市 $ 6 $ 的一名参赛者逆时针移动到城市 $ 4 $。移动成本为 $ 2 \times 1 = 2 $。 - 城市 $ 7 $ 的两名参赛者顺时针移动到城市 $ 1 $。移动成本为 $ 3 \times 2 = 6 $。 最终，所有有会场的城市，其参赛者人数与容纳能力一致，并且所有参赛者都能到达某个会场。总移动成本为 $ 4 + 2 + 6 = 12 $，这就是最小值。 **本翻译由 AI 自动生成**