N гангстеров собираются в ресторан. i-й гангстер приходит в момент времени T и имеет богатство 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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 10 20
10 16
10 11
10 7
|
21
|