Qanqsterlər#850
N sayda gangster restorana toplaşır. -ci gangster T_i zamanında gəlir və sərvəti P_i qədərdir. Restoranın qapıları K + 1 açılma dərəcəsinə malikdir və bu dərəcələr aralığında tam ədədlərlə ifadə olunur. Qapının açılma dərəcəsi hər zaman vahidində bir vahid dəyişə bilər, yəni qapılar bir vahid açıla, bir vahid bağlana və ya olduğu kimi qala bilər. Başlanğıcda qapılar bağlıdır (açılma dərəcəsi ).
-ci gangster yalnız gəldiyi anda qapının açılma dərəcəsi onun dolğunluğuna S_i bərabər olarsa restorana daxil ola bilər. Əks halda, o gəldikdə uyğun deyilsə gedir və qayıtmır.
Restoran zaman intervalında fəaliyyət göstərir.
Məqsəd, gangsterlərin maksimal ümumi sərvətini toplayacaq şəkildə qapını uyğun idarə etməkdir.
Birinci sətirdə N, K, T ədədləri verilir. İkinci sətirdə T_1, T_2, \ldots, T_N ədədləri, üçüncü sətirdə P_1, P_2, \ldots, P_N ədədləri, dördüncü sətirdə isə S_1, S_2, \ldots, S_N ədədləri verilir. Sətirlərdəki ədədlər boşluqla ayrılmışdır.
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; bütün ədədlər tamdır.
Bir ədəd çıxarın — restorana daxil olan gangsterlərin maksimal ümumi sərvəti. Əgər heç kim daxil ola bilməyibsə, çıxarın.
Nümunə 1