Camion di evacuazione
Dopo aver trasportato alcune auto guaste da un paese lontano tramite traghetto, queste sono arrivate in una città vicina. Ora è il momento di trasferirle nella capitale. Poiché sono rotte, possono essere spostate soltanto utilizzando camion di evacuazione.
Si sa che è possibile caricare due auto sullo stesso camion di evacuazione se sono abbastanza leggere, ossia se la somma dei loro pesi non supera una soglia prefissata. In caso contrario, ogni auto deve essere trasportata con un camion di evacuazione dedicato.
Ti vengono fornite
n auto con i rispettivi pesi e una soglia di carico che un camion di evacuazione può sostenere. Il tuo compito è calcolare il numero minimo di camion di evacuazione necessari per trasportare tutte le auto.Ingresso
La prima riga di input contiene due interi
n (2 ≤ n ≤ ) e t (1 ≤ t ≤ ) - il numero di auto e la soglia massima di peso che un camion di evacuazione può trasportare.La riga successiva contiene
n interi separati da spazio (1 ≤ ≤ t), che rappresentano i pesi delle auto.Uscita
Il programma deve stampare il numero minimo di camion di evacuazione necessari per trasferire tutte le auto.
Esempi
Ingresso | Uscita |
4 11
5 8 10 2 | 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB