codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

230A.md (1993B)


      1 Source: https://codeforces.com/problemset/problem/230/A
      2 
      3 A. Dragons
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Kirito is stuck on a level of the MMORPG he is playing now. To move on in the game, he's got to defeat all *n* dragons that live on this level. Kirito and the dragons have strength, which is represented by an integer. In the duel between two opponents the duel's outcome is determined by their strength. Initially, Kirito's strength equals *s*.
     22 
     23 If Kirito starts duelling with the *i*-th (1 ≤ *i* ≤ *n*) dragon and Kirito's strength is not greater than the dragon's strength *x**i*, then Kirito loses the duel and dies. But if Kirito's strength is greater than the dragon's strength, then he defeats the dragon and gets a bonus strength increase by *y**i*.
     24 
     25 Kirito can fight the dragons in any order. Determine whether he can move on to the next level of the game, that is, defeat all dragons without a single loss.
     26 
     27 Input
     28 
     29 The first line contains two space-separated integers *s* and *n* (1 ≤ *s* ≤ 104, 1 ≤ *n* ≤ 103). Then *n* lines follow: the *i*-th line contains space-separated integers *x**i* and *y**i* (1 ≤ *x**i* ≤ 104, 0 ≤ *y**i* ≤ 104) — the *i*-th dragon's strength and the bonus for defeating it.
     30 
     31 Output
     32 
     33 On a single line print "YES" (without the quotes), if Kirito can move on to the next level and print "NO" (without the quotes), if he can't.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 2 2  
     41 1 99  
     42 100 0
     43 ```
     44 
     45 Output
     46 
     47 ```
     48 YES
     49 ```
     50 
     51 Input
     52 
     53 ```
     54 10 1  
     55 100 100
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 NO
     62 ```
     63 
     64 Note
     65 
     66 In the first sample Kirito's strength initially equals 2. As the first dragon's strength is less than 2, Kirito can fight it and defeat it. After that he gets the bonus and his strength increases to 2 + 99 = 101. Now he can defeat the second dragon and move on to the next level.
     67 
     68 In the second sample Kirito's strength is too small to defeat the only dragon and win.