uCoder | 1123 | Nível: 3 | Tempo Limite: 10
O Banco Inteligente
Adaptado por Erich Rodrigues
Competição: OBI 2015, Nível 2, Fase 1
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á 4 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
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
1000 |
34201 |
|
22 |
4 |