XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: arquivos.x, onde x deve ser c, cpp, java, js ou py

Arquivos

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

Informações sobre a pontuação

  • Em um conjunto de casos de teste somando 20 pontos, N ≤ 10
  • Em um conjunto de casos de teste somando 50 pontos, N ≤ 1000

Exemplos

Entrada
3 3
1 2 3
Saída
2
	
Entrada
5 4
4 3 1 2 2
Saída
3
	
Tarefas Programação Nível 1
Promoção
logo sbc
Patrocínio
Apoio
Coordenação