M. Небоскрёбы

Небоскрёбы стоят в ряд слева направо; у $i$-го известны высота $H_i$ и количество монет $G_i$. Игра начинается прыжком на любой небоскрёб; каждым ходом можно прыгнуть на небоскрёб правее текущего, высота которого не меньше текущей. Монеты собираются со всех посещённых. Посчитайте, сколько существует различных наборов посещённых небоскрёбов, дающих не меньше $K$ монет.

Иначе говоря: сколько подмножеств индексов с неубывающими высотами имеют сумму монет не меньше $K$.

В первой строке $N$ и $K$ ($1 \le N \le 36$, $1 \le K \le 4 \cdot 10^{10}$). В каждой из следующих $N$ строк — $H_i$ и $G_i$ ($1 \le H_i, G_i \le 10^9$).

Выведите количество наборов, дающих не меньше $K$ монет.