Задача №631. Гангстеры
\(N\) гангстеров собираются в ресторан. \(i\)-й гангстер приходит в момент времени \(T_i\) и имеет богатство \(P_i\). Дверь ресторана имеет \(K\) + 1 степень открытости, они обозначаются целыми числами из интервала [0, \(K\)]. Степень открытости двери может изменяться на единицу в единицу времени, то есть дверь может открыться на единицу, закрыться на единицу или остаться в том же состоянии. В начальный момент времени дверь закрыта (степень открытости 0). \(i\)-й гангстер заходит в ресторан, только если дверь открыта специально для него, то есть когда степень открытости двери соответствует его полноте \(S_i\). Если в момент, когда гангстер подходит к ресторану, степень открытости двери не соответствует его полноте, он уходит и больше не возвращается. Ресторан работает в интервале времени [0, \(T\)]. Требуется собрать гангстеров с максимальным суммарным богатством в ресторане, открывая и закрывая дверь соответствующим образом.
В первой строке находятся числа \(N\), \(K\), \(T\), во второй - \(T_1\), \(T_2\), ..., \(T_N\), в третьей - \(P_1\), \(P_2\), ..., \(P_N\). в четвёртой - \(S_1\), \(S_2\), ..., \(S_N\). Числа в строках разделены пробелами. 1 <= \(N\) <= 100, 1 <= \(K\) <= 100, 1 <= \(T\) <= 30 000, 0 <= \(T_i\) <= \(T\), 1 <= \(P_i\) <= 300, 1 <= \(S_i\) <= \(K\), все числа целые.
Вывести одно число - максимальное суммарное богатство гангстеров, попавших в ресторан. Если зайти не удалось никому, вывести 0.
2 10 20 10 16 10 11 10 7
21