蓝桥杯2025年第十六届省赛真题-原料采购

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

工厂有一辆运货卡车，其容量为 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 ≤ 5000 ，m ≤ 50000 ； 

对于 60% 的评测用例，m ≤ 10⁵ ； 

对于所有评测用例，1 ≤ n ≤ 10⁵ ，1 ≤ m, o ≤ 10⁹ ，1 ≤ a_i , b_i , c_i ≤ 10⁹ ，保 证对于 i > 1 ，一定有 c_i−1 < c_i 。