1998: Хмарочоси
Перегляд у форматі PDFЧи мріяли ви колись, що ви головний герой комп'ютерної гри? Головний герой цієї історії, Бранімір, саме зараз бачить такий сон.
Світ у сні Браніміра складається з ~N~ хмарочосів, розташованих зліва направо. Для ~i~-го хмарочоса нам відома висота ~H_i~ та кількість золотих монет ~G_i~ на даху хмарочоса. Гра починається зі стрибка на будь-який з хмарочосів і складається з кількох кроків. На кожному кроці Бранімір може стрибнути на хмарочос праворуч від того, на якому він зараз знаходиться (він також може перестрибнути через кілька з них), якщо він не нижчий за поточний. На кожному даху хмарочоса, де він опиняється, Бранімір збирає всі золоті монети.
Бранімір може закінчити гру після будь-якої кількості кроків (також нуль), але він повинен зібрати принаймні ~K~ золотих монет, щоб перейти на наступний рівень.
Бранімір хоче знати кількість різних способів зіграти в гру, щоб перейти на наступний рівень. Дві гри вважаються різними, якщо існує хмарочос, який був відвіданий в одній грі, але не в іншій.
Input
Перший рядок вхідних даних містить додатні цілі числа ~N~ (~1 \leq N \leq 40~) та ~K~ (~1 \leq K \leq 4 \cdot 10^{10}~), числа із задачі.
~i~-й з наступних ~N~ рядків містить два додатні цілі числа, ~H_i~ та ~G_i~ (~1 \leq H_i, G_i \leq 10^9~), числа із задачі.
Output
Ви повинні вивести кількість різних способів зіграти в гру із задачі.
Оцінювання
У тестових випадках вартістю ~40\%~ від загальної кількості балів буде виконуватися ~N \leq 20~.
Sample Input 1
4 6
2 1
6 3
7 2
5 6
Sample Output 1
3
Sample Input 2
2 7
4 6
3 5
Sample Output 2
0
Sample Input 3
4 15
5 5
5 12
6 10
2 1
Sample Output 3
4
Коментарі
в чому полягає особливість 13 тесту? перших 12 проходять менше ніж 0.2с а останній більше 2.
N=40 та мало монет на хмарочосах