你是否曾经梦见自己是电脑游戏中的主角？这个故事的主角 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}。

COCI 2017-2018 CONTEST #2