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

Branimir 梦中的世界由从左到右排列的 $N$ 座摩天大楼组成。对于第 $i$ 座摩天大楼，我们已知其高度 $H_i$ 以及楼顶上的金币数量 $G_i$。游戏开始时，他可以跳到任意一座摩天大楼上，随后进行若干步操作。在每一步中，Branimir 可以跳到当前所在大楼右侧的某座摩天大楼上（也可以跳过中间的一些大楼），前提是目标大楼的高度不低于当前大楼的高度。在他停留的每座摩天大楼楼顶，Branimir 都会收集所有的金币。Branimir 可以在任意步数（也可以是零步）后结束游戏，但他必须收集至少 $K$ 个金币才能晋级到下一关。

Branimir 想知道有多少种不同的游戏方式可以让他晋级到下一关。如果两种游戏方式中，存在某座摩天大楼在其中一种方式中被访问过，而在另一种方式中没有被访问过，则认为这两种游戏方式是不同的。

输入格式

输入的第一行包含正整数 $N$（$1 \le N \le 40$）和 $K$（$1 \le K \le 4 \cdot 10^{10}$）。

接下来的 $N$ 行中，第 $i$ 行包含两个正整数 $H_i$ 和 $G_i$（$1 \le H_i, G_i \le 10^9$）。

输出格式

输出能够晋级到下一关的不同游戏方式的数量。

子任务

对于 $40\%$ 的测试数据，满足 $N \le 20$。

样例

输入样例 1

4 6
2 1
6 3
7 2
5 6

输出样例 1

3

输入样例 2

2 7
4 6
3 5

输出样例 2

0

输入样例 3

4 15
5 5
5 12
6 10
2 1

输出样例 3

4

说明

样例 1 说明：

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