407011: GYM102680 F Calculatus Eliminatus

Memory Limit：1024 MB Time Limit：5 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

F. Calculatus Eliminatustime limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output
When you've mislaid a certain something, keep your cool and don't get hot.

Calculatus Eliminatus is the best friend that you've got!

Calculatus Eliminatus always helps an awful lot;

The way to find a missing something is to find out where it's not.

Mark the places it could be all from $$$1$$$ up to $$$n$$$

–But careful now cuz $$$n$$$ could be up to two billion ten!–

Then cross off all $$$u$$$ ranges, all inclusive start and end,

And you'll know all of the places that the object hasn't been!

We just jot down all the places where it isn't and gee wiz–

Very shortly we will locate where the missing object is!

Input

The first line contain two integers $$$n$$$ and $$$u$$$.

$$$u$$$ lines follow, each containing two integers representing the start and end of a range, respectively (ranges can be overlapping)

$$$1 \leq n \leq 2,000,000,010$$$

$$$0 \leq u \leq 1,000$$$

Output

Output a single integer representing the location of the missing object.

Additional constraint on input: There will only be one possible location it can be.

ExamplesInput
10 3
7 10
1 1
3 8
Output
2
Input
2000000010 2
1 8
10 2000000010
Output
9
Note

For the first sample, after crossing off the relevant ranges, we are left with:

X?XXXXXXXX

So, by using Calculatus Eliminatus, we have found that the missing object must be at position 2. (Notice that ranges can, but need not, overlap)

Source/Category

加入题单

算法标签：