Задача 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