Adilbek and the Watering System

Adilbek 有一个浇水系统。这个浇水系统可以容纳 $c$ 升水，并且在第 $0$ 分钟前有 $c_0$ 升水。 从第 $0$ 分钟前开始，这个浇水系统每分钟都会消耗 $1$ 升水。如果在第 $i$ 分钟前这个浇水系统没有水了，那么我们认为浇水系统在第 $i$ 分钟处于缺水状态。 Adilbek 希望这个浇水系统直到第 $m$ 分钟都有水（即，不处于缺水状态），所以他叫了他 $n$ 个朋友帮忙。第 $i$ 个朋友可以在第 $t_i$ 分钟前送来最多 $a_i$ 升水，并且每送 $1$ 升水就要支付 $b_i$ 元。 这里我们认为送水是立刻完成的，即，如果浇水系统在第 $i$ 分钟前没有水了，但是有一个朋友在第 $i$ 分钟前送了一些水，那么浇水系统在第 $i$ 分钟不位于缺水状态。 Adilbek 不想付太多钱，所以他可以告知他的朋友送多少升水来。假设第 $i$ 个朋友送了 $k_i$ 升水，那么需要满足： - 所有朋友都按照计划送水时，浇水系统直到第 $m$ 分钟都有水。 - $\displaystyle \sum_{i=1}^{n} k_ib_i$ 是所有合法方案中最小的。 帮 Adilbek 算出他最少付多少钱。如果没有一种方案能使得浇水系统直到第 $m$ 分钟都有水，输出 `-1`。

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.

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 < t_i < 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 $ .

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.

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

6
0
-1
4