Description

你是否曾经梦见自己是电脑游戏中的主角？这个故事的主角 Branimir 正在做这样的梦。

在 Branimir 的梦中，世界由 $N$ 座从左到右排列的摩天大楼组成。对于第 $i$ 座摩天大楼，我们知道其高度 $H_i$ 和屋顶上的金币数量 $G_i$。游戏开始时，可以跳到任意一座摩天大楼上，并由此开始多个步骤。在每一步中，Branimir 可以跳到右边的一座摩天大楼上（也可以跳过几座），但前提是它的高度不低于当前所在的摩天大楼。在每座摩天大楼的屋顶上，Branimir 将收集所有的金币。Branimir 可以在任意步数后结束游戏（包括零步），但他必须至少收集 $K$ 个金币才能晋级到下一个关卡。

Branimir 想知道有多少种不同的方式可以玩这个游戏以晋级到下一个关卡。如果在一个游戏中访问了某座摩天大楼，而在另一个游戏中没有访问，则这两个游戏的玩法不同。

Input Format

输入的第一行包含正整数 $N(1\leq N \leq 40)$ 和 $K(1\leq K\leq 4\times 10^{10})$，这些是题目中的数字。

接下来的 $N$ 行中的第 $i$ 行包含两个正整数 $H_i$ 和 $G_i(1\leq H_i,G_i \leq 10^9)$，这些是题目中的数字。

Output Format

你必须输出完成题目所述游戏的不同方式的数量。

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

Hint

示例输出 1 的解释

以下三种游戏方式可以让 Branimir 晋级到下一个关卡（数字表示他访问的摩天大楼的编号）：{1, 2, 3}，{1, 4} 和 {4}。

评分

在总分的 40% 的测试用例中，将满足 $N\leq 20$。（由 ChatGPT 4o 翻译）