410026: GYM103920 D Coats of Paint

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Coats of Painttime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

For National Rock Day, you've decided to paint the rock that you were gifted. This is a peculiar rock that is divided into $$$n$$$ sections, numbered $$$1,...,n$$$. Every second for the next $$$x$$$ seconds, your friend will give you two numbers. The first number will represent the section that you should start painting at and then the second number will represent the section that you should stop painting at (both inclusive). Every coat of paint will have a thickness of 1. Can you find the section with the largest thickness at any point in the rock after all layers of paint have been applied?

Input

The first line contains one number $$$n$$$ ($$$1 \leq n \leq 10^5$$$), representing the number of sections the rock is divided into. The second line contains one number $$$x$$$ ($$$1 \leq x \leq 100$$$), representing the number of times your friend will give you starting and stopping numbers.

The next $$$x$$$ lines will each contain two integers $$$i, j$$$ ($$$1 \leq i \leq j \leq n$$$) representing the starting and stopping sections to paint.

Output

Output the region of the rock that has the greatest thickness (has the most coats of paint). If there are multiple, return the lowest section number.

ExamplesInput
5
1
2 4
Output
2
Input
10
3
3 5
4 8
5 9
Output
5

加入题单

上一题 下一题 算法标签: