Есть n типов гирек. Масса одной гирьки типа i+1 не меньше массы двух гирек типа i. Количество гирек каждого типа равно 2.
Посчитайте количество способов набрать массу ровно W. Два способа считаются различными, если для некоторого i отличается количество использованных гирек типа i.
Исходные данные
В первой строке записано два целых числа n и W — количество типов гирек и масса, которую мы хотим набрать (1 ≤ n ≤ 60, 0 ≤ W ≤ 4 · 1018).
Во второй строке записаны n целых чисел ai — массы гирек. 1 ≤ a1, 2 · ai ≤ ai+1, an ≤ 1018.
Результат
Выведите ответ на задачу в единственной строке.
Пример
исходные данные | результат |
---|
5 100
2 5 10 21 49
| 3
|
Автор задачи: Алексей Данилюк
Источник задачи: Петрозаводск лето 2018. t.me/umnik_team Contest