Динамическое программирование

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

Ограничения: `1\ ≤\ N\ ≤\ 100`, `1\ ≤\ K\ ≤\ 100`, `1\ ≤\ T\ ≤\ 30\ 000`, `0\ ≤\ T_i\ ≤\ T`, `1\ ≤\ P_i\ ≤\ 300`, `1\ ≤\ S_i\ ≤\ K`, все числа целые.

В первой строке находятся числа `N`, `K`, `T`, во второй – `T_1,\ T_2,\ …,\ T_N`, в третьей – `P_1,\ P_2,\ …,\ P_N`. в четвёртой – `S_1,\ S_2,\ …,\ S_N`. Числа в строках разделены пробелами.

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

4 10 20   
10 16 8 16
10 11 15 1
10 7 1 8  

26

2 17 100
5 0     
50 33   
6 1     

0