Abschleppfahrzeuge
Nachdem mehrere defekte Autos mit einer Fähre aus einem fernen Land gebracht wurden, sind sie nun in einer Nachbarstadt angekommen. Jetzt müssen sie in die Hauptstadt transportiert werden. Weil sie nicht fahrbereit sind, können sie nur mit Abschleppfahrzeugen befördert werden.
Es ist bekannt, dass man zwei Autos in ein einziges Abschleppfahrzeug laden kann, sofern ihr kombiniertes Gewicht einen bestimmten Grenzwert nicht überschreitet. Andernfalls benötigt jedes Auto ein eigenes Abschleppfahrzeug.
Gegeben sind
n Autos mit ihren jeweiligen Gewichten sowie ein Grenzwert, den ein Abschleppfahrzeug maximal tragen kann. Gesucht ist die minimale Anzahl an Abschleppfahrzeugen, die benötigt wird, um alle Autos zu transportieren.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n (2 ≤ n ≤ ) und t (1 ≤ t ≤ ) – die Anzahl der Autos und der maximale Grenzwert für das Abschleppfahrzeug.Die nächste Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ t), welche die Gewichte der Autos darstellen.Ausgabe
Das Programm soll die minimale Anzahl an Abschleppfahrzeugen ausgeben, die für den Transport aller Autos benötigt wird.
Beispiele
Input | Output |
4 11
5 8 10 2 | 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB