Într-o sală de sport sunt 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 () se ştie că dacă va fi aprins în culoarea galben, atunci el va lumina cu intensitatea de lumeni, iar dacă va fi aprins în culoarea albastru, atunci va lumina cu 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 , 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 . În cazul în care nu se pot aprinde în culoarea galben becuri de o intensitate totală cel puțin egală cu , atunci se va afişa valoarea .
Date de intrare
Fişierul de intrare becuri.in
conține pe prima linie numerele naturale şi . A doua linie conține numere naturale reprezentând, în ordine, intensitățile becurilor dacă sunt aprinse în culoarea galben. Pe a treia linie sunt numere naturale , 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 în cazul în care nu se pot aprinde becurile astfel încât să fie respectate cerințele.
Restricții și precizări
- , pentru
- Pentru de puncte, .
- Pentru alte de puncte, pentru .
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 , şi , obţinând intensitatea totală . Becurile şi vor fi aprinse în culoarea albastru, obţinând o intensitate totală (maximă posibil).