It is a well known strategy for mobile game ads to show the gameplay of a game in which the player is very bad. This makes the viewer want to download the game to prove how easy it is. You are the tester of one such game: Choice hero.
The idea of the game is the following: you start with a hero with power $$$f$$$ and you are going to play $$$n$$$ levels, numbered from 1 to $$$n$$$, one after the other in ascending order. In the $$$i$$$-th level you fight exactly one of two available monsters. The monster from the left has power $$$a_i$$$ and the monster from the right power $$$b_i$$$. If you successfully beat exactly one of the monsters you proceed to the next level $$$i+1$$$, or you win the game in case it was the $$$n$$$-th and last level. The hero can only beat a monster with power smaller than or equal to his own power at the time. If the hero has power $$$x$$$ before the fight with a monster with power $$$y$$$ ($$$y \leq x$$$), the hero gains the power of the defeated monster, that is, his power becomes $$$x+y$$$. Your job as the tester is to report if it is possible to win the game given the list of $$$n$$$ levels.
The first line of the input contains two integers $$$n$$$ and $$$f$$$, the number of levels and the initial power of the hero ($$$1 \leq n \leq 2 \cdot 10^3 , 1 \leq f \leq 10^6$$$). The next $$$n$$$ lines contain 2 integers each: $$$a_i$$$ and $$$b_i$$$, the power of the monster from the left and the power of the monster from the right ($$$1 \leq a_i, b_i \leq 10^6$$$).
Print "S" if it is possible to beat the $$$n$$$ levels in the given order or "N" otherwise.
3 2 1 2 5 3 4 4
S
3 2 4 4 1 2 5 3
N
| 2023 USP Try-outs |
|---|
| Закончено |
