Алекс выбирает мастер-классы научного фестиваля. Мастер-класс i идёт с момента sᵢ до момента fᵢ и приносит vᵢ баллов опыта. Чтобы получить баллы, его нужно посетить целиком.
Абонемент Алекса позволяет посетить не более K мастер-классов. Одновременно находиться на двух нельзя. Если один закончился ровно в момент начала другого, можно посетить оба. Переходы между аудиториями мгновенны.
Найдите максимальную сумму баллов опыта, которую можно получить с этим абонементом.
Входные данные
Первая строка содержит целые числа n и K (1 ≤ n ≤ 50 000, 1 ≤ K ≤ min(30, n)). Следующие n строк содержат целые числа sᵢ, fᵢ, vᵢ (0 ≤ sᵢ < fᵢ ≤ 109, 1 ≤ vᵢ ≤ 109). Порядок произвольный; совпадения времён допустимы.
Выходные данные
Выведите максимальную сумму баллов.
Пояснения к примерам
Пример 1. Лучше посетить только шестой мастер-класс. Цепочка 1, 3, 5 дала бы 26 баллов, но требует трёх посещений.
Пример 2. Из трёх совместимых мастер-классов нужно выбрать два: второй и третий.
| № | Входные данные | Выходные данные |
|
1
|
6 2
1 3 7
2 5 12
3 6 9
5 7 8
6 9 10
1 9 24
|
24
|
|
2
|
3 2
0 2 5
2 4 6
4 6 7
|
13
|