Популярная сеть быстрого питания «McDuck's» открыла новый филиал в Берляндии. В ресторане установлено k плит. Для того чтобы приготовить бургер, надо жарить котлету в течение минуты на одной из плит, поэтому ресторан может готовить не более k бургеров в минуту.
Известно, что в «McDuck's» придут n клиентов. i-й из них придёт в момент времени t
i, закажет x
i бургеров и будет готов заплатить за них c
i бурлей. Каждый клиент готов ждать заказ в течение w минут и, если через w минут после прихода он не получил x
i бургеров, он не заплатит ничего. При этом каждый клиент готов получать только свежие бургеры, то есть только те, котлеты для которых были поджарены не раньше времени t
i. Из-за таких сложных требований ресторан не всегда сможет выполнить все заказы всех клиентов.
Менеджеров ресторана заинтересовало, какую максимальную прибыль может получить «McDuck's». Помогите им ответить на этот непростой вопрос. Можно считать, что на готовку бургеров не расходуется никаких денег.
Входные данные
В первой строке содержатся три целых числа n, k и w (1 ≤ n ≤ 100000, 1 ≤ k ≤ 10, 1 ≤ w ≤ 60) — число клиентов, число плит и время ожидания клиента, соответственно.
Следующие n строк содержат описания клиентов, состоящие из трёх целых чисел — t
i, x
i, c
i (1 ≤ t
i, x
i, c
i ≤ 10
9) — время (в минутах) прихода i-го клиента, число бургеров, которые он закажет и число бурлей, которые он готов заплатить, соответственно. Клиенты перечислены в порядке возрастания времени прихода, то есть для любого i > 1 верно, что t
i−1 ≤ t
i.
Выходные данные
В единственной строке выведите одно число — максимальную прибыль ресторана.
Примечание
В первом тестовом примере первую котлету можно поставить жариться в момент времени 0 и тогда в момент времени 1 она будет готова и её можно будет дать в бургере первому клиенту. В момент времени 1 можно поставить жариться ещё одну котлету, она будет готова в момент времени 2 и её можно будет дать в бургере второму клиенту.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 1 1
1 1 5
1 1 7 |
12 |
| 2 |
3 2 2
1 6 8
2 5 10
3 4 4 |
12 |