Ресторан.

В ресторане собираются N посетителей. Посетитель с номером i, имеющий сумму денег Pi и полноту Si,
подходит к двери ресторана во время Ti. Входная дверь ресторана имеет K состояний открытости.
Состояние открытости двери может изменяться на одну единицу за единицу времени: дверь открывается
на единицу или остается в том же состоянии. В начальный момент времени дверь закрыта(состояние 0). Посетитель с номером i входит в ресторан только в том случае, если дверь открыта специально для него, то есть когда состояние открытости двери совпадает с его степенью полноты Si. Если в момент прихода посетителя состояние двери не совпадает с его степенью полноты, то посетитель уходит и больше не возвращается.
Ресторан работает в течение времени T.
Требуется, правильно открывая и закрывая дверь, добиться того, чтобы за время работы ресторана в нем собрались посетители, общая сумма денег у которых максимальна.

Технические требования:
Входные данные - устройство стандартного ввода.
Выходные данные - устройство стандартного вывода.
Ограничение по времени тестирования: 5 секунд на один тест.

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

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

Выводится одно число - максимальная сумма денег у посетителей ресторана. В случае, если нельзя добиться прихода в ресторан ни одного посетителя, выходной файл должен содержать значение 0.

Пример N1 входных данных   Пример N2 входных данных
4 10 20     2 17 100
10 16 8 16   5 0  
10 11 15 1   50 33  
10 7 1 8   10 10  
Результат N1:   Результат N2:
26   0