Dragons · Interview Problem

Back to problems

Codeforces

Easy

Greedy

Sorting

Arrays

Dragons

Defeat a sequence of dragons by training enough strength and then gaining their power.

Acceptance 0%

Start Practice

Also Available On

Other platform versions and source mappings for the same problem.

Codeforces 230A

gfg

Primary

Problem Statement

Problem

You start with an initial strength $s$ . There are $n$ dragons, each described by a strength requirement $x_i$ and a bonus power $y_i$ .

You may defeat dragons in any order. To defeat a dragon, your current strength must be strictly greater than its requirement. After defeating it, your strength increases by its bonus power.

Determine whether you can defeat all dragons.

Task

Choose an order of fighting so that every dragon can be defeated, or report that it is impossible.

Input Format

The first line contains two integers $s$ and $n$ .
The next $n$ lines each contain two integers $x_i$ and $y_i$ describing a dragon.

Output Format

Print YES if you can defeat all dragons.
Otherwise print NO.

Constraints

$1 \le n$ is small enough for a straightforward greedy solution.
$1 \le s, x_i, y_i$ are positive integers.
Use the condition that your strength must be strictly greater than the dragon's requirement.

Examples

Sample cases returned by the problem API.

Example 1

Input

2 2
1 99
100 1

Output

YES

Explanation

Fight the dragon requiring 1 first: strength becomes 101, so the second dragon is also beatable.

Example 2

Input

10 1
100 1

Output

NO

Explanation

Your strength never exceeds 100, so the only dragon cannot be defeated.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress