ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2123. Рюкзак

Ограничение времени: 4.0 секунды
Ограничение памяти: 256 МБ
Есть n типов гирек. Масса одной гирьки типа i+1 не меньше массы двух гирек типа i. Количество гирек каждого типа равно 2.
Посчитайте количество способов набрать массу ровно W. Два способа считаются различными, если для некоторого i отличается количество использованных гирек типа i.

Исходные данные

В первой строке записано два целых числа n и W — количество типов гирек и масса, которую мы хотим набрать (1 ≤ n ≤ 60, 0 ≤ W ≤ 4 · 1018).
Во второй строке записаны n целых чисел ai — массы гирек. 1 ≤ a1, 2 · aiai+1, an ≤ 1018.

Результат

Выведите ответ на задачу в единственной строке.

Пример

исходные данныерезультат
5 100
2 5 10 21 49
3
Автор задачи: Алексей Данилюк
Источник задачи: Петрозаводск лето 2018. t.me/umnik_team Contest