В ресторане собираются 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 |