← 返回题目列表

Codeforces · 1238/G

G. Adilbek 和浇水系统

中文机器翻译题面 查看原题

阿迪贝克必须给他的花园浇水。他将在复杂的浇水系统的帮助下完成这项工作:他只需向其供水,其余的工作将由这些机制完成。

浇水系统每分钟消耗一升水(如果没有水,则不工作)。它最多可容纳 $$$c$$$ 升。 Adilbek 已将 $$$c_0$$$ 升水倒入系统中。他现在要开始给花园浇水,浇水 $$$m$$$ 分钟,并且在第 $$$i$$$ 分钟开始时,浇水系统应至少含有一升水(对于从 $$$0$$$ 到 $$$m - 1$$$ 的每 $$$i$$$)。

现在阿迪贝克想知道如果浇水系统没水了他该怎么办。他打电话给他的朋友$$$n$$$并询问他们是否要带一些水。第$$$i$$$个朋友回答说他最多可以带$$$a_i$$$升水;他将在第$$$t_i$$$分钟开始时到达,并将他拥有的所有水倒入系统中(如果系统无法容纳这么多水,则将多余的水倒出);然后他会要求 Adilbek 为他带来的每升水支付 $$$b_i$$$ 美元。您可以假设,如果一个朋友在第 $$$t_i$$$ 分钟开始时到达,并且系统在同一分钟开始时耗尽了水,则该朋友倒水的速度足够快,以便系统不会停止工作。

当然,Adilbek 不想付钱给他的朋友,但他必须给花园浇水。所以他必须告诉他的朋友们应该带多少水。形式上,Adilbek 希望选择 $$$n$$$ 整数 $$$k_1$$$、$$$k_2$$$、...、$$$k_n$$$,方式如下:

- 如果每个朋友 $$$i$$$ 携带恰好 $$$k_i$$$ 升水,则浇水系统在浇灌花园所需的整个时间内都将工作;
- 总和 $$$\sum\limits_{i = 1}^{n} k_i b_i$$$ 是可能的最小值。

帮助 Adilbek 确定他必须支付给朋友的最低金额,或者确定 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$$$ 好友到达时间,最大水量第 $$$i$$$ 位朋友可以携带,第 $$$i$$$ 位朋友提供 $$$1$$$ 升的费用。

保证所有查询的所有 $$$n$$$ 之和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个查询,打印一个整数 - Adilbek 必须向他的朋友支付的最低金额,或者如果 Adilbek 在 $$$m$$$ 分钟内无法给花园浇水,则为 $$$-1$$$。

示例

输入 #1

4
1 5 4 2
2 4 2
0 4 5 4
2 5 3 1
1 2 4
3 1 3
2 3 5 1
2 1 1
1 4 3

输出 #1

6
0
-1
4