Задача C. Гангстеры
N гангстеров собираются в ресторан. i-й гангстер приходит в
момент времени Ti и имеет богатство
Pi. Дверь ресторана имеет K + 1
степень открытости, они обозначаются целыми числами из интервала
[0, K]. Степень открытости двери может изменяться на единицу
в единицу времени, то есть дверь может открыться на единицу, закрыться
на единицу или остаться в том же состоянии. В начальный момент времени дверь
закрыта (степень открытости 0). i-й гангстер заходит в ресторан, только
если дверь открыта специально для него, то есть когда степень открытости
двери соответствует его полноте Si. Если в момент,
когда гангстер подходит к ресторану, степень открытости двери не соответствует
его полноте, он уходит и больше не возвращается. Ресторан работает в интервале
времени [0, T]. Требуется собрать гангстеров с максимальным
суммарным богатством в ресторане, открывая и закрывая дверь соответствующим
образом.
Ограничения: 1 <= N <= 100,
1 <= K <= 100,
1 <= T <= 30 000,
0 <= Ti <= T,
1 <= Pi <= 300,
1 <= Si <= K,
все числа целые, время 2 с.
Ввод из файла gangster.in. В первой строке находятся числа N,
K, T,
во второй -
T1, T2, ..., TN,
в третьей -
P1, P2, ..., PN.
в четвёртой -
S1, S2, ..., SN.
Числа в строках разделены пробелами.
Вывод в файл gangster.out. Вывести одно число - максимальное суммарное
богатство гангстеров, попавших в ресторан. Если зайти не удалось никому,
вывести 0.
Примеры
Ввод 1 Ввод 2
4 10 20 2 17 100
10 16 8 16 5 0
10 11 15 1 50 33
10 7 1 8 6 1
Вывод 1 Вывод 2
26 0