Après avoir transporté plusieurs voitures en panne depuis un pays lointain à l’aide d’un ferry, elles sont maintenant arrivées dans une ville voisine. Il est temps de les acheminer vers la capitale. Étant donné qu’elles sont hors d’usage, elles ne peuvent être déplacées que par des camions d’évacuation.
On sait qu’il est possible de charger deux voitures dans un seul camion d’évacuation si elles sont suffisamment légères, c’est-à-dire si la somme de leurs poids ne dépasse pas un certain seuil. Dans le cas contraire, chaque voiture doit être transportée par un camion distinct.
On vous donne n voitures avec leurs poids respectifs ainsi qu’un seuil de poids maximal que peut supporter un camion d’évacuation. Votre tâche est de calculer le nombre minimal de camions nécessaires pour transporter toutes les voitures.
Entrée
La première ligne de l’entrée contient deux entiers n (2 ≤ n ≤ ) et t (1 ≤ t ≤ ) – le nombre de voitures et la charge maximale qu’un camion peut supporter.
La ligne suivante contient n entiers séparés par des espaces (1 ≤ ≤ t) représentant les poids de chaque voiture.
Sortie
Le programme doit afficher le nombre minimal de camions d’évacuation nécessaires pour transporter toutes les voitures.