题目背景

搬运自 COCI 2017/2018 Contest #2 T4「San」，原题题面。

根据原题，时间限制 1 秒，空间限制 64 MB，满分 120 分。

题目描述

Have you ever dreamt that you were the main character in a computer game? The protagonist of this story, Branimir, is having that dream right now.

The world in Branimir's dream consists of $N$ skyscrapers ordered from left to right. For the $i^{th}$ skyscraper, we know the height $H_i$ and the number of gold coins $G_i$ on the roof of the skyscraper. The game begins with a jump on any of the skyscrapers and consists of several steps. In each step, Branimir can jump on a skyscraper to the right from the one he's currently on (it is possible for him to jump over a couple of them too) and if it is not lower than the current one. On each skyscraper roof he's on, Branimir will collect all the gold coins. Branimir can end the game after any number of steps (zero as well), but he must collect at least $K$ gold coins in order to advance to the next level.

Branimir wants to know the number of different ways for him to play the game in order to advance to the next level. Two games are played in different ways if there is a skyscraper that was visited in one game, and not in the other.

输入格式

The first line of input contains positive integers $N(1\leq N \leq 40)$ and $K(1\leq K\leq 4\times 10^{10}$), the numbers from the task.

The $i^{th}$ of the following $N$ lines contains two positive integers, $H_i$ and $G_i(1\leq H_i,G_i \leq 10^9$), the numbers from the task.

输出格式

You must output the number of different ways to play the game from the task.

题目大意

有 $N$ 栋楼从左到右排列，第 $i$ 栋楼的高度为 $H_i$，楼上有 $G_i$ 个金币。

玩家可以从任意一个楼开始，每一步可以从当前位置向右跳到任意不低于当前楼的高度的楼上。然后可以获得每栋楼上的金币。

玩家可以一直跳，并且随时结束游戏，但是要保证获得的金币数 $\geq K$。

现在想知道共有多少不同的方案。

输入格式：

第一行输入 $N,K$。

接下来 $N$ 行，每行两个整数，表示 $H_i,G_i$。

对于 $40\%$ 的数据，有 $N\leq 20$。

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

提示

Explanation for Sample Output 1

The following three games will take Branimir to the next level (the numbers represent the labels of the skyscrapers he visited): {1, 2, 3}, {1, 4} and {4}.

Scoring

In test cases worth 40% of total points, it will hold $N\leq 20$.