Qanqsterlər
N sayda gangster restorana toplaşır. i-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 [0, K] 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 0). i-ci gangster yalnız qapılar onun üçün uyğun açıldıqda, yəni qapının açılma dərəcəsi onun dolğunluğuna S_i bərabər olduqda restorana daxil ola bilər. Əgər gangster gəldiyi zaman qapının açılma dərəcəsi onun dolğunluğuna uyğun deyilsə, o, gedir və geri qayıtmır.
Restoran [0, T] zaman intervalında fəaliyyət göstərir.
Məqsəd, gangsterlərin maksimum ümumi sərvətini restoranda toplamaq üçün qapıları uyğun şəkildə açıb bağlamaqdır.
Giriş verilənləri
Birinci sətirdə N, K, T ədədləri verilir. İkinci sətirdə T_1, T_2, ..., T_N ədədləri, üçüncü sətirdə P_1, P_2, ..., P_N ədədləri, dördüncü sətirdə isə S_1, S_2, ..., S_N ədədləri verilir. Sətirlərdəki ədədlər boşluqla ayrılmışdır.
1 ≤ N ≤ 100; 1 ≤ K ≤ 100; 1 ≤ T ≤ 30 000; 0 ≤ T_i ≤ T; 1 ≤ P_i ≤ 300; 1 ≤ S_i ≤ K; bütün ədədlər tamdır.
Çıxış verilənləri
Bir ədəd çıxarın - restorana daxil olan gangsterlərin maksimum ümumi sərvəti. Əgər heç kim daxil ola bilməyibsə, 0 çıxarın.