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

Антон решил подготовиться к очередной олимпиаде. Чтобы Антону было интереснее, Илья подготовил для него $$$n$$$ задач. Сдать $$$i$$$-ю задачу можно только в первые $$$d_{i}$$$ дней, причем сдавать несколько задач в один и тот же день нельзя. Илья оценил полезность $$$i$$$-й задачи как $$$r_{i}$$$, и разделил задачи на три темы, тема $$$i$$$-й задачи равна $$$type_{i}$$$.

Антон хочет решить ровно $$$a$$$ задач на первую тему, ровно $$$b$$$ на вторую тему и ровно $$$c$$$ задач на третью тему (и каждая из этих задач должна быть решена не позже своего дедлайна). Скажите Антону, сможет ли он это сделать, и если сможет, то выведите максимальную суммарную полезность задач, которые он решит.

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

В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержатся четыре целых числа $$$n, a, b, c$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le a, b, c \le n$$$).

В каждой из следующих $$$n$$$ строк содержатся три целых числа $$$r_i, type_i, d_i$$$ ($$$0 \le r_i \le 10^{9}$$$, $$$1 \le type_i \le 3$$$, $$$1 \le d_i \le n$$$).

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

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

Для каждого набора входных данных выведите единственное число: $$$-1$$$, если решить нужный набор задач невозможно, и максимальную полезность решенных задач в противном случае.

Пример
Входные данные
4
4 1 1 0
1 2 1
1 1 1
0 1 2
1 2 2
3 1 1 1
1 1 2
7 2 1
9 3 2
4 2 1 0
100 2 1
5 2 3
7 1 2
5 1 2
5 1 1 1
10 3 1
9 2 3
20 1 1
16 1 4
1 3 4
Выходные данные
2
-1
17
35
Примечание

В первом наборе входных данных выгодно решить $$$2$$$-ю и $$$4$$$-ю задачи.

Во втором наборе входных данных ответа не существует.

В третьем наборе входных данных оптимально решить $$$2$$$-ю, $$$3$$$-ю и $$$4$$$-ю задачи.

В последнем наборе входных данных оптимально решить $$$1$$$-ю, $$$2$$$-ю и $$$4$$$-ю задачи.