CF1238G Adilbek and the Watering System

Adilbek 需要给他的花园浇水。他打算用一个复杂的浇水系统来完成这项工作：他只需要把水送到系统里，剩下的工作都由机械装置完成。 该浇水系统每分钟消耗 $1$ 升水（如果没有水，系统就无法工作）。系统最多能容纳 $c$ 升水。Adilbek 已经向系统中倒入了 $c_0$ 升水。他打算现在就开始浇水，并持续浇水 $m$ 分钟。要求在每一分钟开始时（即对于每个 $i$，$0 \le i < m$），系统中至少要有 $1$ 升水。 现在 Adilbek 担心浇水系统会用完水。他联系了 $n$ 个朋友，询问他们是否能带些水来。第 $i$ 个朋友回答说，他最多能带 $a_i$ 升水；他会在第 $t_i$ 分钟开始时到达，并把他带来的所有水倒进系统（如果系统无法容纳这么多水，多余的水会溢出）；然后他会要求 Adilbek 按每升 $b_i$ 美元支付费用。你可以假设，如果某个朋友在第 $t_i$ 分钟开始时到达，而系统也正好在这一分钟开始时用完了水，这位朋友加水的速度足够快，不会导致系统停止工作。 当然，Adilbek 不想多花钱，但他必须完成浇水任务。因此，他需要告诉每个朋友应该带多少水。形式化地说，Adilbek 需要选择 $n$ 个整数 $k_1, k_2, \ldots, k_n$，使得： - 如果第 $i$ 个朋友带来恰好 $k_i$ 升水，那么浇水系统能在整个浇水时间内正常工作； - $\sum\limits_{i=1}^{n} k_i b_i$ 的值尽可能小。 请帮助 Adilbek 计算他最少需要支付多少钱，或者判断他是否无法完成 $m$ 分钟的浇水任务。 你需要回答 $q$ 个独立的询问。

第一行包含一个整数 $q$（$1 \le q \le 5 \cdot 10^5$），表示询问的数量。 每个询问的第一行包含四个整数 $n, m, c, c_0$（$0 \le n \le 5 \cdot 10^5, 2 \le m \le 10^9, 1 \le c_0 \le c \le 10^9$），分别表示朋友的数量、浇水的分钟数、浇水系统的容量和 Adilbek 已经倒入的水量。 接下来的 $n$ 行，每行包含三个整数 $t_i, a_i, b_i$（$0 < t_i < m, 1 \le a_i \le c, 1 \le b_i \le 10^9$），分别表示第 $i$ 个朋友到达的时间、他最多能带的水量以及每升水的价格。 保证所有询问中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每个询问，输出一个整数，表示 Adilbek 最少需要支付多少钱。如果无法完成 $m$ 分钟的浇水任务，输出 $-1$。

由 ChatGPT 4.1 翻译