Rezolvare PBinfo #4585

Î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 ≤ i ≤ N) se ştie că dacă va fi aprins în culoarea galben, atunci el va lumina cu intensitatea de gi lumeni, iar dacă va fi aprins în culoarea albastru, atunci va lumina cu ai 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ța

Scrieţi un program care, cunoscând intensităţile becurilor atunci când sunt aprinse în 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 sau egală 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 N numere naturale g1, g2, …, gN reprezentând, în ordine, intensităţile becurilor dacă sunt aprinse în culoarea galben. Pe a treia linie sunt N numere naturale a1, a2, …, aN, 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 ≤ N, K ≤ 2000
• 1 ≤ ai , gi ≤ 100, pentru 1 ≤ i ≤ N

Exemplu:

becuri.in

5 10
1 2 4 5 7
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ă 11. Becurile 2 şi 5 vor fi aprinse în culoarea albastru, obţinând o intensitate totală 12 (maximă posibil).