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

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

O Banco Inteligente

Caixas automáticos nos bancos são uma invenção ótima mas, às vezes, a gente precisa de dinheiro trocado e a máquina entrega notas de R$100,00. Outras vezes, a gente quer sacar um valor um pouco maior e por questões de segurança gostaria de receber tudo em notas de R$100,00, mas a máquina entrega um monte de notas de R$20,00. O Banco Inteligente está tentando minimizar esse problema dando aos clientes a possibilidade de escolher o valor das notas na hora do saque. Para isso, eles precisam da sua ajuda para saber, dado o valor S do saque e quantas notas de cada valor a máquina tem, quantas formas distintas existem de entregar o valor S. O banco disponibiliza notas de 2, 5, 10, 20, 50 e 100. Por exemplo, se S = 22 e o número de notas de cada valor é N2 = 5, N5 = 4, N10 = 3, N20 = 10, N50 = 0 e N100 = 10, então há quatro formas distintas da máquina entregar o valor do saque:

  • 20 + 2,
  • 10 + 10 + 2,
  • 10 + 5 + 5 + 2 e
  • 5 + 5 + 5 + 5 + 2.

Entrada

A primeira linha da entrada contém um inteiro S, o valor do saque. A segunda linha contém seis inteiros N2, N5, N10, N20, N50 e N100, respectivamente, o número de notas de valores 2, 5, 10, 20, 50 e 100, disponíveis na máquina.

Saída

Seu programa deve imprimir um inteiro, o número de formas distintas da máquina entregar o saque.

Restrições

  • 0 ≤ S ≤ 5000 e Ni ≤ 500

Informações sobre a pontuação

  • Em um conjunto de casos de teste somando 20 pontos, N ≤ 1000 e Ni ≤ 30
  • Em um conjunto de casos de teste somando 40 pontos, N ≤ 1000 e Ni ≤ 50

Exemplos

Entrada
22
5 4 3 10 0 10
Saída
4
	
Entrada
1000
20 20 20 20 20 20
Saída
34201
	
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação