Jumping

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

The world your friend’s A. dream consists of $n$ skyscrapers ordered from left to right. For the $i(1\le i\le n)$-th skyscraper, we know the height $h_i$ and the number of gold $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, your friend A. 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 the lower than the current one. On each skyscraper roof he’s on, your friend A. will collect all the gold coins. Your friend A. can end the game after the number of steps (zero as well), but he must collect at least $k$ gold coins to advance to the next level.

Your friend. A wants to know the number of different ways for him to play the game 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.

Input

The first line contains positive integers $n(1\le n\le 40)$ and $k(1\le k\le 4\cdot 10^{10})$, the numbers from the task.

Each of the following $n$ lines contains two positive integers $h_i$ and $g_i(1\le h_i,g_i\le 10^9)$, the numbers from the task.

Output

Print the number of different ways to play the game.

Examples

Consider the first test case. The following three games will take your friend А. to the next level (the numbers represent the labels of the skyscrapers he visited): $\{1,2,3\},\{1,4\}$ and $\{4\}$.