Задача Moneybox
В скарбничці героя олімпіад Василька Пупкіна є лише монети його улюблених номіналів. Кількість улюблених номіналів N (1≤N≤7) (маються на увазі українські монети номіналом 1, 2, 5, 10, 25, 50 коп. та 1 грн. Монету номіналом 1 грн. вважати монетою номіналом 100 коп.). Одного разу Васильку конче були потрібні гроші, і він вирішив дістати зі скарбнички з допомогою пінцета частину монет. Звичайно, Василько не бачить монет в скарбничці, і тому щоразу може вийняти монету будь-якого номіналу. Скількох різних значень може набути сума отриманих Васильком грошей, якщо він дістане зі скарбнички M (1≤M≤1000) монет (вважати, що кількість монет кожного з наявних в скарбничці номіналів не менша M)? Наприклад, улюблені монети Василька 10 коп. і 25 коп. (N=2). Василько виймає 3 монети (M=3). При цьому можливі варіанти:
10 коп. + 10 коп. + 10 коп. = 30 коп;
10 коп. + 10 коп. + 25 коп. = 45 коп;
10 коп. + 25 коп. + 25 коп. = 60 коп;
25 коп. + 25 коп. + 25 коп. = 75 коп.
Тобто, можливі чотири різні значення суми.
Технічні умови: Програма читає число N, далі N чисел Z1, Z2, … Zn – номінали монет у копійках , далі число M. Всі числа записані в один рядок через пропуск. Програма виводить на екран єдине число – шукану величину.
Приклади:
Введення: 2 10 25 3
Виведення: 4
Введення: 4 1 2 5 10 3
Виведення: 19
|
