N vedete merg la un restaurant. Vedeta i ajunge la momentul de timp T_i, are venitul V_i milioane $ si are rating-ul R_i.
Usa restaurantului are K+1 grade de deschidere reprezentate prin numerele naturale din intervalul [0, K]. Initial usa este inchisa (ceea ce reprezinta gradul de deschidere 0). La fiecare minut usa poate ramane la acelasi grad de deschidere sau gradul de deschidere se poate modifica cu 1 (creste sau scade).
Vedeta i intra in restaurant numai daca usa este deschisa special pentru ea (gradul de deschidere a usii coincide cu ratingul vedetei). In caz contrar, vedeta nu intra in restaurant si nu se va mai intoarce niciodata.
Restaurantul functioneaza in intervalul de timp [0, T] (toti timpii fiind exprimati in minute).

Cerinţă

Scrieti un program care sa determine suma maxima a veniturilor vedetelor care pot intra in restaurant.

Date de intrare

Fisierul de intrare vedete.in contine pe prima linie trei numere naturale separate prin spatiu N K T (cu semnificatia din enunt). Pe cea de a doua linie sunt scrise N numere naturale separate prin cate un spatiu T₁ T₂ ... T_N reprezentand momentele de timp la care sosesc vedetele. Pe cea de a treia linie sunt scrise N numere naturale separate prin cate un spatiu V₁ V₂ ... V_N reprezentand in ordine veniturile celor N vedete. Pe cea de a patra linie sunt scrise N numere naturale separate prin cate un spatiu R₁ R₂ ... R_N reprezentand in ordine rating-urile celor N vedete.

Date de ieşire

Fisierul de iesire vedete.out va contine o singura linie pe care va fi scris un singur numar natural reprezentand suma veniturilor vedetelor care pot intra in restaurant (maxima posibil).

Restricţii

• 0<N<=100
• 1<K<=100
• 0<=T<=30000
• 0<=T_i<=T
• 0<=V_i<=300
• 0<=R_i<=K

Exemple

vedete.in	vedete.out
3 5 100 5 1 2 10 1 15 4 0 2	25

prof. Emanuela Cerchez

Liceul de Informatică „Grigore Moisil” Iaşi

emanuela.cerchez@gmail.com