Se citesc n greutati ale unor persoane si limita maxima de greutate G a unei barci. Fiecare barca poate transporta cel mult 2 persoane, daca suma greutatilor lor nu depaseste G. Determinati, folosind metoda Greedy, numarul minim de barci necesare pentru a transporta toate persoanele.
- Date de intrare
- Pe prima linie se citesc n si G. Pe a doua linie se citesc cele n greutati (fiecare cel mult G).
- Date de iesire
- Se afiseaza un singur numar: numarul minim de barci necesare.
- Restrictii
- 1 <= n <= 100000, 1 <= greutate <= G <= 10^9
Exemple
Exemplul 1
Intrare
4 5 3 2 2 1
Iesire
2
Exemplul 2
Intrare
3 3 3 2 2
Iesire
3