Problem Description

Imagine you are the protagonist in a computer game. In this game, there are \( N \) skyscrapers arranged from left to right. The \( i \)-th skyscraper has a height of \( H_i \) and \( G_i \) gold coins on its roof.

The player can start from any skyscraper and can jump to any skyscraper to the right that is not lower than the current one. Each time the player lands on a skyscraper, they collect all the gold coins on it.

The player can end the game at any time but must ensure that the total number of gold coins collected is at least \( K \).

The task is to determine the number of different ways the player can play the game to collect at least \( K \) gold coins. Two games are considered different if there is a skyscraper that was visited in one game but not in the other.

Input Format

The first line of input contains two positive integers \( N \) and \( K \), where \( N \) is the number of skyscrapers and \( K \) is the minimum number of gold coins required.

The next \( N \) lines each contain two positive integers \( H_i \) and \( G_i \), representing the height and the number of gold coins on the \( i \)-th skyscraper, respectively.

Output Format

Output a single integer representing the number of different ways to play the game to collect at least \( K \) gold coins.

Sample Input and Output

Sample Input #1

4 6
2 1
6 3
7 2
5 6

Sample Output #1

3

Sample Input #2

2 7
4 6
3 5

Sample Output #2

0

Sample Input #3

4 15
5 5
5 12
6 10
2 1

Sample Output #3

4

Notes/Hints

Explanation for Sample Output 1

The following three games will take the player to the next level (the numbers represent the labels of the skyscrapers visited): {1, 2, 3}, {1, 4}, and {4}.

Scoring

In test cases worth 40% of the total points, \( N \leq 20 \).

见题面 Input 部分

见题面 Output 部分