becuri

Time limit: 0.2s Memory limit: 64MB Input: becuri.in Output: becuri.outPoints by default: 10p

Într-o sală de sport sunt NN 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 ii (1iN1 \leq i \leq N) se ştie că dacă va fi aprins în culoarea galben, atunci el va lumina cu intensitatea de gig_i lumeni, iar dacă va fi aprins în culoarea albastru, atunci va lumina cu aia_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 KK, 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 KK. În cazul în care nu se pot aprinde în culoarea galben becuri de o intensitate totală cel puțin egală cu KK, atunci se va afişa valoarea 1-1.

Date de intrare

Fişierul de intrare becuri.in conține pe prima linie numerele naturale NN şi KK. A doua linie conține ii numere naturale g1,g2,,gNg_1, g_2, \dots, g_N reprezentând, în ordine, intensitățile becurilor dacă sunt aprinse în culoarea galben. Pe a treia linie sunt NN numere naturale a1,a2,,aNa_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-1 în cazul în care nu se pot aprinde becurile astfel încât să fie respectate cerințele.

Restricții și precizări

  • 1N,K2 0001 \leq N,K \leq 2 \ 000
  • 1ai,gi1001 \leq a_i,g_i \leq 100, pentru 1iN1 \leq i \leq N
  • Pentru 3030 de puncte, N20N \leq 20.
  • Pentru alte 3030 de puncte, gi=1g_i = 1 pentru 1iN1 \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 11, 33 şi 44, obţinând intensitatea totală 1010. Becurile 22 şi 55 vor fi aprinse în culoarea albastru, obţinând o intensitate totală 1212 (maximă posibil).

Log in or sign up to be able to send submissions!