|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Фёдор Меньшиков, ВГПУ.
Сложность Бета
N гангстеров собираются в ресторан. i-й гангстер приходит в
момент времени Ti и имеет богатство
Pi. Дверь ресторана имеет K + 1
степень открытости, они обозначаются целыми числами из интервала
[0, K]. Степень открытости двери может изменяться на единицу
в единицу времени, то есть дверь может открыться на единицу, закрыться
на единицу или остаться в том же состоянии. В начальный момент времени дверь
закрыта (степень открытости 0). i-й гангстер заходит в ресторан, только
если дверь открыта специально для него, то есть когда степень открытости
двери соответствует его полноте Si. Если в момент,
когда гангстер подходит к ресторану, степень открытости двери не соответствует
его полноте, он уходит и больше не возвращается. Ресторан работает в интервале
времени [0, T]. Требуется собрать гангстеров с максимальным
суммарным богатством в ресторане, открывая и закрывая дверь соответствующим
образом.
Ввод
В первой строке находятся числа N, K, T,
во второй -
T1, T2, ..., TN,
в третьей -
P1, P2, ..., PN.
в четвёртой -
S1, S2, ..., SN.
Числа в строках разделены пробелами.
Вывод
Вывести одно число - максимальное суммарное богатство гангстеров,
попавших в ресторан. Если зайти не удалось никому, вывести 0.
Ограничения
1 ≤ N ≤ 100; 1 ≤ K ≤ 100; 1 ≤ T ≤ 30 000;
0 ≤ Ti ≤ T;
1 ≤ Pi ≤ 300;
1 ≤ Si ≤ K; все числа целые.
|
Ввод 1
|
Ввод 2
|
4 10 20
10 16 8 16
10 11 15 1
10 7 1 8
|
2 17 100
5 0
50 33
6 1
|
|
Вывод 1
|
Вывод 2
|
26
|
0
|
Для отправки решений необходимо выполнить вход.
|