Гангстери#850
гангстерів збираються до ресторану. -й гангстер приходить у момент часу T_i із багатством P_i. Двері ресторану мають K + 1 ступенів відчиненості, позначених цілими числами з інтервалу . Протягом однієї одиниці часу ступінь відчиненості дверей може змінюватися не більше ніж на одиницю: двері можуть відчинитися на одиницю, зачинитися на одиницю або залишитися у тому ж стані. На початку двері зачинені (ступінь відчиненості ).
-й гангстер зайде в ресторан лише якщо на момент його приходу ступінь відчиненості дверей дорівнює його повноті S_i. В іншому разі він йде і не повертається.
Ресторан працює у проміжку часу .
Потрібно зібрати гангстерів з максимальним сумарним багатством, коректно керуючи дверима.
У першому рядку задано числа , , . У другому рядку — T_1, T_2, \ldots, T_N. У третьому — P_1, P_2, \ldots, P_N. У четвертому — S_1, S_2, \ldots, S_N. Числа у рядках розділені пробілами.
1 \leq N \leq 100; 1 \leq K \leq 100; 1 \leq T \leq 30000; 0 \leq T_i \leq T; 1 \leq P_i \leq 300; 1 \leq S_i \leq K; всі числа цілі.
Виведіть одне число — максимальне сумарне багатство гангстерів, які потрапили до ресторану. Якщо ніхто не зайшов, виведіть .
Приклад 1