Descrição
Aldo tem N arquivos em seu computador, cada um com um tamanho em bytes. Ele quer dividir estes arquivos em pastas, porém o sistema do computador é velho e só aceita pastas com as duas seguintes limitações:
• Uma pasta pode ter no máximo dois arquivos
• A soma dos tamanhos dos arquivos na pasta não pode exceder B bytes
Como ele tem muitos arquivos ele prefere não criar muitas pastas. Dado o tamanho dos arquivos, calcule o número mínimo possível de pastas.
Vamos supor um exemplo que temos os arquivos de tamanho 1, 2 e 3, e que o limite de bytes seja 3. A solução é colocar os dois primeiros arquivos juntos, totalizando apenas 2 pastas.
Entrada
A entrada consiste de duas linhas. A primeira linha contém os números inteiros N e B. A segunda linha contém N inteiros indicando o tamanho de cada arquivo.
Saída
Seu programa deve escrever uma única linha na saída, contendo um único número inteiro, a quantidade mínima possível de pastas.
Restrições
• 1 ≤ N ≤ 105
• 1 ≤ B ≤ 109
• Os arquivos terão tamanho entre 1 e B, inclusive
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
5 4 |
3 |
|
3 3 |
2 |
Efetue Login ou Cadastre-se para submeter uma solução.
Adaptado por Erich Rodrigues | Competição: OBI 2015, Nível 1, Fase 1