CF1238G.Adilbek and the Watering System

Adilbek has to water his garden. He is going to do it with the help of a complex watering system: he only has to deliver water to it, and the mechanisms will do all the remaining job.

The watering system consumes one liter of water per minute (if there is no water, it is not working). It can hold no more than $c$ liters. Adilbek has already poured $c_0$ liters of water into the system. He is going to start watering the garden right now and water it for $m$ minutes, and the watering system should contain at least one liter of water at the beginning of the $i$-th minute (for every $i$ from $0$ to $m - 1$).

Now Adilbek wonders what he will do if the watering system runs out of water. He called $n$ his friends and asked them if they are going to bring some water. The $i$-th friend answered that he can bring no more than $a_i$ liters of water; he will arrive at the beginning of the $t_i$-th minute and pour all the water he has into the system (if the system cannot hold such amount of water, the excess water is poured out); and then he will ask Adilbek to pay $b_i$ dollars for each liter of water he has brought. You may assume that if a friend arrives at the beginning of the $t_i$-th minute and the system runs out of water at the beginning of the same minute, the friend pours his water fast enough so that the system does not stop working.

Of course, Adilbek does not want to pay his friends, but he has to water the garden. So he has to tell his friends how much water should they bring. Formally, Adilbek wants to choose $n$ integers $k_1$, $k_2$, ..., $k_n$ in such a way that:

• if each friend $i$ brings exactly $k_i$ liters of water, then the watering system works during the whole time required to water the garden;
• the sum $\sum\limits_{i = 1}^{n} k_i b_i$ is minimum possible.

Help Adilbek to determine the minimum amount he has to pay his friends or determine that Adilbek not able to water the garden for $m$ minutes.

You have to answer $q$ independent queries.

阿迪尔别克需要给他的花园浇水。他将借助一套复杂的浇水系统来完成这项工作：他只需向系统供水，其余工作均由系统自动完成。

该浇水系统每分钟消耗 1 升水（若无水，则系统停止工作）。系统容量上限为 $c$ 升。阿迪尔别克已向系统中注入了 $c_0$ 升水。他将立即开始浇水，并持续 $m$ 分钟；且对每个 $i$（其中 $i$ 从 $0$ 到 $m-1$），在第 $i$ 分钟开始时，系统中必须至少剩余 1 升水。

现在阿迪尔别克担心浇水系统会中途缺水。他联系了 $n$ 位朋友，询问他们是否愿意送水。第 $i$ 位朋友答复称：他最多可运送 $a_i$ 升水；他将在第 $t_i$ 分钟开始时抵达，并将所带全部水量倒入系统（若系统剩余容量不足以容纳该水量，则超出部分被直接倒掉）；随后他会向阿迪尔别克收取每升水 $b_i$ 美元的费用。你可以假设：若某位朋友在第 $t_i$ 分钟开始时抵达，而系统恰好也在同一时刻耗尽水量，则该朋友倒水速度足够快，确保系统不会因此中断工作。

显然，阿迪尔别克不愿向朋友们付钱，但他又必须完成花园浇水任务。因此，他需要告知每位朋友应运送多少水。形式化地，阿迪尔别克需选择 $n$ 个整数 $k_1, k_2, \dots, k_n$，使得：

• 若每位朋友 $i$ 恰好运送 $k_i$ 升水，则整个 $m$ 分钟浇水过程中，浇水系统始终正常工作；
• 总费用 $\sum\limits_{i = 1}^{n} k_i b_i$ 达到最小可能值。

请帮助阿迪尔别克计算他需向朋友们支付的最少金额；若无法保证系统连续工作 $m$ 分钟，请判定该情况。

你需要回答 $q$ 个相互独立的查询。

The first line contains one integer $q$ ($1 \le q \le 5 \cdot 10^5$) – the number of queries.

The first line of each query contains four integers $n, m, c$ and $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$) — the number of friends, the number of minutes of watering, the capacity of the watering system and the number of liters poured by Adilbek.

Each of the next $n$ lines contains three integers $t_i, a_i, b_i$ ($ 0 \lt t_i \lt m, 1 \le a_i \le c, 1 \le b_i \le 10^9$) — the $i$-th friend's arrival time, the maximum amount of water $i$-th friend can bring and the cost of $1$ liter from $i$-th friend.

It is guaranteed that sum of all $n$ over all queries does not exceed $5 \cdot 10^5$.

第一行包含一个整数 $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$），分别表示朋友人数、浇水总时长（分钟）、浇水系统的容量以及阿迪尔别克倒入的水量（升）。

接下来的 $n$ 行，每行包含三个整数 $t_i, a_i, b_i$（$0 \lt t_i \lt m$, $1 \le a_i \le c$, $1 \le b_i \le 10^9$），表示第 $i$ 位朋友的到达时间、第 $i$ 位朋友最多能带来的水量（升）以及从第 $i$ 位朋友处获取 1 升水的花费。

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

For each query print one integer — the minimum amount Adilbek has to pay his friends, or $-1$ if Adilbek is not able to water the garden for $m$ minutes.

对于每个查询，输出一个整数——Adilbek 需要付给朋友们的最少金额；如果 Adilbek 无法让花园持续浇水 $m$ 分钟，则输出 $-1$。