题目描述

小蓝负责一家工厂的原料采购。

工厂有一辆运货卡车，其容量为 $m$。

工厂附近的采购点都在同一条路的同一方向上，一共有 $n$ 个，每个采购点和工厂的距离各不相同。其中，第 $i$ 个采购点的价格为 $a_i$, 库存为 $b_i$, 距离为 $c_i$。

卡车每行驶一单位长度的路径就需要额外花费 $o$。（返程没有花费，你也可以认为 $o$ 实际是行驶两单位长度的花费）

请计算将卡车装满最少需要花费多少钱，如果没有任何方案可以装满请输出 $-1$。

输入格式

输入的第一行包含三个正整数 $n, m, o$，相邻整数之间使用一个空格分隔。

接下来 $n$ 行，每行包含三个正整数 $a_i, b_i, c_i$ 表示一个采购点，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案，即装满卡车所需的最小花费。

3 5 1
99 9 1
3 4 99
1 2 190

201

提示

评测用例规模与约定

• 对于 $40\%$ 的评测用例，$n \leq 5000$, $m \leq 50000$;
• 对于 $60\%$ 的评测用例，$m \leq 10^5$;
• 对于所有评测用例，$1 \leq n \leq 10^5$, $1 \leq m, o \leq 10^9$, $1 \leq a_i, b_i, c_i \leq 10^9$, 保证对于 $i > 1$, 一定有 $c_{i-1} < c_i$。