Caminhões de evacuação
Depois de transportar vários carros avariados de um país distante por ferry, eles chegaram a uma cidade vizinha. Agora é hora de levá-los até a capital. Como estão avariados, só podem ser transportados por caminhões de evacuação.
Sabe-se que dois carros cabem em um único caminhão de evacuação se forem suficientemente leves—ou seja, se a soma dos seus pesos não ultrapassar um determinado limite. Caso contrário, cada carro precisará ser transportado por um caminhão dedicado.
É fornecida uma lista de
n carros, com os respetivos pesos, e um valor limite que cada caminhão de evacuação consegue suportar. O seu objetivo é determinar o número mínimo de caminhões de evacuação necessários para transportar todos os carros.Entrada
A primeira linha da entrada contém dois inteiros
n (2 ≤ n ≤ ) e t (1 ≤ t ≤ ), que representam o número de carros e o limite máximo de peso que um caminhão de evacuação consegue suportar.A linha seguinte contém
n inteiros separados por espaço, (1 ≤ ≤ t), correspondentes aos pesos dos carros.Saída
O programa deve imprimir o número mínimo de caminhões de evacuação necessário para transportar todos os carros.
Exemplos
Entrada | Saída |
4 11
5 8 10 2 | 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB