Задача №113813. Небоскрёбы
Вы когда-нибудь мечтали стать главным героем компьютерной игры? Главный герой этой истории, Бранимир, мечтает сейчас именно об этом.
Мир в мечте Бранимира состоит из N небоскребов, пронумерованных слева направо. Для i -го небоскреба, известна его высота H i и количество золотых монет G i на крыше этого небоскреба. Игра начинается с прыжка на любой из небоскребов и состоит из нескольких ходов. На каждом ходу Бранимир может прыгнуть на любой небоскрёб, находящийся справа от него, но так, чтобы высота нового небоскрёба была не меньше того небоскрёба, на котором сейчас сидит Бранимир. Оказавшись на крыше небоскреба, Бранимир собирает все золотые монеты на ней. Бранимир может закончить игру после любого количества шагов (возможно, нулевого), но он должен собрать не менее K золотых монет, чтобы перейти на следующий уровень.
Бранимир хочет узнать, сколько существует способов сыграть в эту игру так, чтобы перейти на следующий уровень. Две игры называются разными, если существует небоскреб который был посещен в одной игре, но не был посещён в другой.
Первая строка содержит 2 натуральных числа N и K ( 1 ≤ N ≤ 40 , 1 ≤ K ≤ 4·10 10 ) — число небоскрёбов и количество монет, которые надо набрать соответственно.
Следующие N строк содержат информацию о небоскрёбах. В i -й строке даны 2 числа H i и G i ( 1 ≤ H i , G i , ≤ 10 9 ) — высота и количество монет на i -м небоскрёбе.
В единственной строке вывода выведите число возможных игр, в которых Бранимир сможет пройти на следующий уровень.
Решение, корректно работающее при n ≤ 20 будет оцениваться в 40 баллов.
4 6 2 1 6 3 7 2 5 6
3
2 7 4 6 3 5
0
4 15 5 5 5 12 6 10 2 1
4