Branimir's Skyscraper Adventure

Branimir dreams that he is the protagonist of a computer game. In his dream, the world consists of \(N\) skyscrapers arranged in a row from left to right. For the \(i^{th}\) skyscraper, its height is \(H_i\) and there are \(G_i\) gold coins on its roof.

The game starts by choosing any skyscraper to jump on. Afterwards, in each move, Branimir may jump to any skyscraper to the right (possibly skipping some) provided that its height is not less than the height of the skyscraper he is currently on. On landing, he collects all the coins present on the roof of that skyscraper.

Branimir can stop playing at any moment (even immediately after his first jump), but in order to advance to the next level he must have collected at least \(K\) coins. Two games are considered different if there is at least one skyscraper that is visited in one game and not in the other.

Your task is to compute the number of different ways Branimir can play the game such that he collects at least \(K\) coins. Each valid game corresponds to a unique nonempty sequence of skyscrapers that he visits (following the rules above) whose total coins sum up to at least \(K\).

inputFormat

The first line contains two integers \(N\) and \(K\) -- the number of skyscrapers and the minimum number of coins required, respectively.

The following \(N\) lines each contain two integers \(H_i\) and \(G_i\) indicating the height and the number of coins on the \(i^{th}\) skyscraper.

outputFormat

Output a single integer -- the number of different ways for Branimir to play the game such that he collects at least \(K\) coins.

sample

3 5
1 3
2 2
3 5

5