P10884 [COCI 2017/2018 #2] San

搬运自 [COCI 2017/2018 Contest #2](https://hsin.hr/coci/archive/2017_2018/) T4「San」，[原题题面](https://hsin.hr/coci/archive/2017_2018/contest2_tasks.pdf)。 根据原题，时间限制 1 秒，空间限制 64 MB，满分 120 分。

你是否曾经梦见自己是电脑游戏中的主角？这个故事的主角 Branimir 正在做这样的梦。 在 Branimir 的梦中，世界由 $N$ 座从左到右排列的摩天大楼组成。对于第 $i$ 座摩天大楼，我们知道其高度 $H_i$ 和屋顶上的金币数量 $G_i$。游戏开始时，可以跳到任意一座摩天大楼上，并由此开始多个步骤。在每一步中，Branimir 可以跳到右边的一座摩天大楼上（也可以跳过几座），但前提是它的高度不低于当前所在的摩天大楼。在每座摩天大楼的屋顶上，Branimir 将收集所有的金币。Branimir 可以在任意步数后结束游戏（包括零步），但他必须至少收集 $K$ 个金币才能晋级到下一个关卡。 Branimir 想知道有多少种不同的方式可以玩这个游戏以晋级到下一个关卡。如果在一个游戏中访问了某座摩天大楼，而在另一个游戏中没有访问，则这两个游戏的玩法不同。

输入的第一行包含正整数 $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)$，这些是题目中的数字。

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

#### 示例输出 1 的解释 以下三种游戏方式可以让 Branimir 晋级到下一个关卡（数字表示他访问的摩天大楼的编号）：{1, 2, 3}，{1, 4} 和 {4}。 #### 评分 在总分的 40% 的测试用例中，将满足 $N\leq 20$。（由 ChatGPT 4o 翻译）