San

Time limit1sMemory limit64 MB

Summary

Count subsets of skyscrapers forming a non-decreasing-height left-to-right jump sequence whose gold sum reaches at least K.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Sorting
Solved: No attempts yet

Problem

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

The world in Branimir's dream consists of $N$ skyscrapers lined up from left to right. Skyscraper $i$ has height $H_i$ , and $G_i$ gold coins lie on its roof.

The game starts when Branimir jumps onto any one of the skyscrapers, and it continues through a number of steps. In one step Branimir can jump onto a skyscraper that stands to the right of the one he is on and is not lower than it. He may jump over the skyscrapers in between. On every roof he lands on, he collects all the gold coins. He can end the game after any number of steps, zero included, but he must collect at least $K$ gold coins to advance to the next level.

Count the number of different ways for Branimir to play the game and advance to the next level. Two games are different if some skyscraper is visited in one of them and not in the other.

Input

The first line contains integers $N$ and $K$ ( $1 \le N \le 40$ , $1 \le K \le 4 \times 10^{10}$ ).

The $i$ -th of the next $N$ lines contains integers $H_i$ and $G_i$ ( $1 \le H_i, G_i \le 10^9$ ), describing skyscraper $i$ .

Output

Print the number of different ways to play the game and advance to the next level.

Hint

In the first example there are three ways to advance. Written as the labels of the visited skyscrapers, they are {1, 2, 3}, {1, 4} and {4}.

Examples3

Example 1
Input
```
4 6
2 1
6 3
7 2
5 6
```
Expected output
```
3
```
Example 2
Input
```
2 7
4 6
3 5
```
Expected output
```
0
```
Example 3
Input
```
4 15
5 5
5 12
6 10
2 1
```
Expected output
```
4
```