| Central Russia Regional Contest, 2022 |
|---|
| Закончено |
У Славы есть набор $$$N$$$ чисел: $$$x_1, x_2, x_3, \dots, x_n$$$. За один ход он может выбрать непустой набор $$$y_1, y_2, y_3, \dots, y_m$$$, такой, что для любого $$$i$$$ от $$$1$$$ до $$$m$$$ $$$y_i$$$ содержится в наборе $$$x_1, x_2, \dots, x_n$$$, и после этого добавить в набор $$$X$$$ сумму всех произведений чисел во всех подмножествах $$$y_1, y_2, \dots, y_m$$$. Славу интересует вопрос: сколько существует чисел, не превосходящих $$$L$$$, которые можно получить при помощи вышеописанной операции, за конечное число действий. (Для лучшего понимания условия, смотрите примечание)
В первой строке входных данных содержатся числа $$$N$$$ и $$$L$$$ $$$(2 \le N \le 20, 1 \le L \le 10^{12})$$$.
Во второй строке содержатся $$$N$$$ чисел $$$x_i$$$ $$$(2 \le x_i \le 15)$$$
В единственной строке выведите число – количество чисел, не превосходящих $$$L$$$, которые можно получить при помощи вышеописанной операции, за конечное число действий.
3 7 2 2 3
2
2 100 14 15
2
Рассмотрим набор чисел $$$X = [14, 15], L = 100$$$
Мы можем выбрать набор $$$Y$$$ так:
$$$[14], [15], [14, 14], [14, 15], [15, 15], [14, 14, 14], \dots$$$
Тогда получим числа:
$$$14 + 14 + 14 * 14 = 224$$$
$$$15 + 15 + 15 * 15 = 255$$$
$$$14 = 14$$$
$$$15 = 15$$$
$$$14 + 15 + 14 * 15 = 239$$$
$$$14 + 14 + 14 + 14 * 14 + 14 * 14 + 14 * 14 + 14 * 14 * 14 = 3374$$$
$$$\dots$$$
Но среди этих чисел, есть всего $$$2$$$, не превосходящие $$$100:~14,~15$$$.
| Название |
|---|


