Într-o sală de sport sunt $N$ becuri. Fiecare bec poate fi aprins în exact una dintre două culori: galben sau albastru. În funcție de culoarea în care este aprins un bec, acesta luminează cu o anumită intensitate.
Pentru fiecare bec $i$ ($1 \leq i \leq N$) se ştie că dacă va fi aprins în culoarea galben, atunci el va lumina cu intensitatea de $g_i$ lumeni, iar dacă va fi aprins în culoarea albastru, atunci va lumina cu $a_i$ lumeni. Şeful sălii de sport doreşte să aprindă becurile astfel încât suma intensităților becurilor aprinse în culoarea galben să fie cel puțin egală cu $K$, iar suma intensităților becurilor aprinse în culoarea albastru să fie cât mai mare.

Cerinţă

Scrieți un program care, cunoscând intensitățile becurilor atunci când sunt aprinse în una din cele două culori, determină suma maximă a intensităților becurilor care vor fi aprinse în culoarea albastru, ținând cont că suma intensităților becurilor aprinse în culoarea galben trebuie să fie mai mare decât $K$. În cazul în care nu se pot aprinde în culoarea galben becuri de o intensitate totală cel puțin egală cu $K$, atunci se va afişa valoarea $-1$.

Date de intrare

Fişierul de intrare becuri.in conține pe prima linie numerele naturale $N$ şi $K$. A doua linie conține $i$ numere naturale $g_1, g_2, \dots, g_N$ reprezentând, în ordine, intensitățile becurilor dacă sunt aprinse în culoarea galben. Pe a treia linie sunt $N$ numere naturale $a_1, a_2, \dots, a_N$, reprezentând, în ordine, intensitățile becurilor atunci când sunt aprinse în culoarea albastru.

Date de ieşire

Fişierul de ieşire becuri.out va conține o singură linie pe care va fi scrisă suma maximă a intensităților becurilor aprinse în culoarea albastru, respectând cerințele din enunţ sau valoarea $-1$ în cazul în care nu se pot aprinde becurile astfel încât să fie respectate cerințele.

Restricții și precizări

• $1 \leq N,K \leq 2 \ 000$
• $1 \leq a_i,g_i \leq 100$, pentru $1 \leq i \leq N$
• Pentru $30$ de puncte, $N \leq 20$.
• Pentru alte $30$ de puncte, $g_i = 1$ pentru $1 \leq i \leq N$.

Exemplu

becuri.in

5 10
1 2 4 5 6
1 4 3 2 8

becuri.out

12

Explicație

Pot fi aprinse în culoarea galben becurile $1$, $3$ şi $4$, obţinând intensitatea totală $10$. Becurile $2$ şi $5$ vor fi aprinse în culoarea albastru, obţinând o intensitate totală $12$ (maximă posibil).