레이팅 미적용Have you ever dreamt that you were the main character in a computer game? The
protagonist of this story, Branimir, is having that dream right now.
The world in Branimir’s dream consists of \(N\) skyscrapers ordered from left to right. For the \(i^{th}\)
skyscraper, we know the height \(H_{i}\) and the number of gold coins \(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, Branimir 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 lower
than the current one. On each skyscraper roof he’s on, Branimir will collect all the gold coins.
Branimir can end the game after any number of steps (zero as well), but he must collect at
least \(K\) gold coins in order to advance to the next level.
Branimir wants to know the number of different ways for him to play the game in order 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.
In test cases worth 40% of total points, it will hold \(N \le 20\).
The first line of input contains positive integers \(N\) (\(1 \le N \le 40\)) and \(K\) (\(1 \le K \le 4 \cdot 10^{10}\)), the
numbers from the task.
The \(i^{th}\) 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.
You must output the number of different ways to play the game from the task.
4 6
2 1
6 3
7 2
5 6
3
2 7
4 6
3 5
0
4 15
5 5
5 12
6 10
2 1
4