Антон решил подготовиться к очередной олимпиаде. Чтобы Антону было интереснее, Илья подготовил для него \(n\) задач. Сдать \(i\)-ю задачу можно только в первые \(d_{i}\) дней, причем сдавать несколько задач в один и тот же день нельзя. Илья оценил полезность \(i\)-й задачи как \(r_{i}\), и разделил задачи на три темы, тема \(i\)-й задачи равна \(type_{i}\).
Антон хочет решить ровно \(a\) задач на первую тему, ровно \(b\) на вторую тему и ровно \(c\) задач на третью тему (и каждая из этих задач должна быть решена не позже своего дедлайна). Скажите Антону, сможет ли он это сделать, и если сможет, то выведите максимальную суммарную полезность задач, которые он решит.
Выходные данные
Для каждого набора входных данных выведите единственное число: \(-1\), если решить нужный набор задач невозможно, и максимальную полезность решенных задач в противном случае.
Примечание
В первом наборе входных данных выгодно решить \(2\)-ю и \(4\)-ю задачи.
Во втором наборе входных данных ответа не существует.
В третьем наборе входных данных оптимально решить \(2\)-ю, \(3\)-ю и \(4\)-ю задачи.
В последнем наборе входных данных оптимально решить \(1\)-ю, \(2\)-ю и \(4\)-ю задачи.
Примеры
| № | Входные данные | Выходные данные |
|
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
|