Camions d’évacuation (evacuation trucks)

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.

download.jpg

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.

Exemples

Entrée

Sortie

4 11
5 8 10 2

3

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue