Стрибки

Ви коли-небудь мріяли стати головним героєм комп'ютерної гри? Головному герою цієї історії, вашому другу А., зараз сниться саме такий сон.

Світ сну вашого друга А. складається з $n$ хмарочосів, розташованих зліва направо. Для $i$-го хмарочоса ($1\le i\le n$) відома висота $h_i$ та кількість золота $g_i$ на даху. Гра починається зі стрибка на будь-який з хмарочосів і складається з кількох кроків. На кожному кроці ваш друг А. може стрибнути на хмарочос праворуч від того, на якому він зараз знаходиться (він може перестрибнути і через кілька з них), за умови, що новий хмарочос не нижчий за поточний. На кожному даху хмарочоса ваш друг А. збере всі золоті монети. Гра може завершитися після певної кількості кроків (включно з нулем), але він повинен зібрати не менше $k$ золотих монет, щоб перейти на наступний рівень.

Ваш друг А. хоче знати, скільки різних способів є для нього зіграти в гру, щоб перейти на наступний рівень. Дві гри вважаються різними, якщо є хоча б один хмарочос, який був відвіданий в одній грі, але не був відвіданий в іншій.

Вхідні дані

У першому рядку записані натуральні числа $n(1\le n\le 40)$ та $k(1\le k\le 4\cdot 10^{10})$ — параметри задачі.

Кожен з наступних $n$ рядків містить два натуральних числа $h_i$ та $g_i(1\le h_i,g_i\le 10^9)$ — характеристики хмарочосів.

Вихідні дані

Виведіть кількість різних способів проходження гри.

Приклади

Розглянемо перший тест. Наступні три варіанти гри дозволять вашому другу А. перейти на наступний рівень (цифри позначають номери хмарочосів, які він відвідав): $\{1,2,3\},\{1,4\}$ та $\{4\}$.