G. Адилбек и система полива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Адилбеку нужно полить свой сад. Он собирается сделать это с помощью сложной системы полива: ему нужно только доставить воду, а механизмы выполнят всю оставшуюся работу.

Система полива потребляет один литр воды в минуту (если воды нет, она не работает). Она может вместить не более $$$c$$$ литров воды. Адилбек уже налил в систему $$$c_0$$$ литров воды. Он собирается начать поливать сад прямо сейчас и поливать его в течение $$$m$$$ минут, а система полива должна содержать не менее одного литра воды в начале $$$i$$$-й минуты (для каждого $$$i$$$ от $$$0$$$ до $$$m - 1$$$).

Адилбеку интересно, что он будет делать, если в системе полива кончится вода. Он позвонил $$$n$$$ своим друзьям и спросил их, могут ли они принести воды. $$$i$$$-й друг ответил, что он может принести не более $$$a_i$$$ литров воды; он придет в начале $$$t_i$$$-й минуты и выльет всю воду, которая у него есть, в систему (если система не может вместить такое количество воды, избыток воды выливается); а затем он попросит Адилбека заплатить $$$b_i$$$ долларов за каждый литр воды, который он принес. Можете считать, что если друг прибывает в начале $$$t_i$$$-й минуты, а в начале той же минуты в системе заканчивается вода, друг наливает воду достаточно быстро, чтобы система не перестала работать.

Конечно, Адилбек не хочет платить своим друзьям, но ему нужно поливать сад. Поэтому он должен сказать своим друзьям, сколько воды они должны принести. Формально Адилбек хочет выбрать $$$n$$$ целых чисел $$$k_1$$$, $$$k_2$$$, ..., $$$k_n$$$ таким образом, чтобы:

  • если друг $$$i$$$ приносит ровно $$$k_i$$$ литров воды, то система полива работает в течение всего времени, необходимого для полива сада;
  • сумма $$$\sum\limits_{i = 1}^{n} k_i b_i$$$ минимально возможна.

Помогите Адилбеку определить минимальную сумму, которую он должен заплатить своим друзьям, или определите, что Адилбеку не удастся поливать сад в течение $$$m$$$ минут.

Вам нужно ответить на $$$q$$$ независимых запросов.

Входные данные

Первая строка содержит целое число $$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$) — количество запросов.

Первая строка каждого запроса содержит четыре целых числа $$$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$$$) — количество друзей, количество минут полива, вместимость системы и количество литров, которое налил Адилбек.

Следующие $$$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$$$-й друг и стоимость $$$1$$$ литра воды у $$$i$$$-го друга.

Гарантируется, что сумма $$$n$$$ по всем запросам не превосходит $$$5 \cdot 10^5$$$.

Выходные данные

На каждый запрос выведите одно целое число — минимальную сумму, которую Адилбек должен заплатить своим друзьям, или $$$-1$$$, если Адилбеку не удастся поливать сад в течение $$$m$$$ минут.

Пример
Входные данные
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