Adilbek and the Watering System

题意翻译

       浇水系统每分钟消耗一升水(如果没有水，它就不能工作)。它最多只能装 c 升。Adilbek已经向系统中注入了 c0 升水。他现在要开始给花园浇水 m 分钟。灌溉系统在第i分钟前应该包含至少一升的水。        Adilbek想知道如果供水系统没水了怎么办，他会给朋友打电话，问他们是否要带水来。第i位朋友说：他最多带ai升水，在第ti分钟前到达（水全部倒入系统中，多余的被浪费），然后他会要求Adilbek为他带来的每公升水支付bi美元。        可以知道，倒水的速度非常快，若朋友第i分钟前到达，而系统在第i分钟前恰好没水了，它依旧可以在第i分钟正常工作。        Adilbek不想多付钱，所以他应该告诉朋友，他应该带多少水来，这用k1,k2...kn来表示 - 如果每一个朋友带齐ki升水，则系统可以一直工作满m分钟 - ∑ (i=1~n)ki*bi ：是最少付的钱        帮助Adilbek算出他最少要付的钱，或者确定系统最少不能工作几分钟

题目描述

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.

输入输出样例

输入样例 #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