Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Гангстеры

(Время: 1 сек. Память: 16 Мб Сложность: 44%)

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

Требуется собрать гангстеров с максимальным суммарным богатством в ресторане, открывая и закрывая дверь соответствующим образом.

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

В первой строке входного файла INPUT.TXT находятся числа N, K, T, во второй - T1, T2, ..., TN, в третьей - P1, P2, ..., PN. в четвёртой - S1, S2, ..., SN. Числа в строках разделены пробелами. Ограничения: 1 ≤ N ≤ 100, 1 ≤ K ≤ 100, 1 ≤ T ≤ 30 000, 0 ≤ Ti ≤ T, 1 ≤ Pi ≤ 300, 1 ≤ Si ≤ K .

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

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

Примеры

INPUT.TXTOUTPUT.TXT
14 10 20
10 16 8 16
10 11 15 1
10 7 1 8
26
22 17 100
5 0
50 33
6 1
0

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483