Camiones de evacuación
Después de trasladar varios autos averiados desde un país lejano en un ferry, llegaron a una ciudad vecina. Ahora toca llevarlos hasta la capital. Dado que los autos están dañados, solo pueden ser transportados con camiones de evacuación.
Se sabe que pueden caber dos autos en un mismo camión de evacuación siempre que sean lo bastante livianos, es decir, si la suma de sus pesos no supera un cierto umbral. De lo contrario, cada auto tendrá que transportarse en un camión separado.
Se te dan
n autos con sus respectivos pesos y un límite máximo de peso que un camión de evacuación puede manejar. Tu tarea es calcular cuántos camiones de evacuación se necesitan como mínimo para trasladar todos los autos.Entrada
La primera línea de la entrada contiene dos números enteros
n (2 ≤ n ≤ ) y t (1 ≤ t ≤ ): la cantidad de autos y el límite de peso que pueden manejar los camiones de evacuación.La siguiente línea contiene
n números enteros separados por espacios (1 ≤ ≤ t), que representan los pesos de los autos.Salida
El programa debe imprimir el número mínimo de camiones de evacuación necesarios para transportar todos los autos.
Ejemplos
Entrada | Salida |
4 11
5 8 10 2 | 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB