Descriere

Fiind date \(n\) obiecte, fiecare cu o valoare \(v_i\) și cu o greutate \(g_i\), determinați ce obiecte trebuie să punem într-un rucsac în care încape o greutată maximă egală cu \(C\) unități, astfel încât suma valorilor obiectelor incluse să fie maximă. Pentru fiecare obiect, singurele opțiuni disponibile sunt să îl includem cu totul în rucsac sau să nu îl luăm deloc.

Date de intrare

Se citesc de la tastatură două numere naturale \(n\) și \(C\), cu semnificațile din enunț. Pe următoarea linie se vor citi \(n\) numere naturale (\(v_1\), \(v_2\), \(\dots\), \(v_n\)), reprezentând valorile obiectelor, iar pe cealaltă încă \(n\) numere naturale (\(g_1\), \(g_2\), \(\dots\), \(g_n\)), reprezentând greutățile obiectelor.

Date de iesire

Se va afișa un număr natural, reprezentând valoarea maximă pe care o putem obține punând obiecte în rucsac.

Restricții și precizări

• \(1 \leq n \leq 1000\)
• \(1 \leq C \leq 1000\)
• \(1 \leq v_i, g_i \leq 100\)

Exemplul 1

Input

3 7
7 3 5
5 3 4

Output

8

Explicație

Valoarea maximă se obține punând în rucsac al doilea și al treilea obiect, care împreună acoperă complet rucsacul și au o valoare combinată egală cu \(3 + 5 = 8\). Dacă am fi ales primul obiect, nu am mai fi putut include niciun dintre celelalte două obiecte, iar valoarea totală ar fi fost doar \(7\).

Exemplul 2

Input

5 10
7 15 4 8 9
3 6 1 1 2

Output

36

Explicație

Valoarea maximă se obține punând în rucsac toate obiectele în afară de primul. Avem \(15 + 4 + 8 + 9 = 36\).

Exemplul 3

Input

4 15
6 7 8 5
1 2 3 4

Output

26

Explicație

Valoarea maximă se obține punând toate obiectele în rucsac, pentru o valoare totală egală cu \(6 + 7 + 8 + 5 = 26\). În acest caz, obiectele pe care le avem la dispoziție nu ocupă capacitatea disponibilă a rucsacului.