페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3835
서브태스크

PS를 하는 학생들 1s 128MB

문제

총 N명의 학생이 일렬로 나란히 서있다.

정올이는 한글이에게 Q번에 걸쳐 다음과 같은 질문을 했다.

“왼쪽으로부터 s_i​번째 학생부터 e_i​번째 학생 사이(양끝 포함)에 PS(Problem Solving)를 하는 학생은 몇 명이야?”

놀랍게도 한글이는 모든 질문에 대해 항상 “한 명”이라고 답했다.

한글이의 모든 대답이 사실이라고 할 때, N명의 학생 중 PS를 하는 학생 수의 최댓값을 구하여라.
만약 어떤 배치로도 모든 질문의 답이 동시에 참이 될 수 없다면 -1을 출력하라.


입력

첫 줄에 정수 N, Q가 주어진다.

둘째 줄부터 Q개의 줄에 걸쳐, i번째 질문을 나타내는 두 정수 s_i, e_i​가 주어진다.

[제약 조건]

  • 1≤N≤200\,000

  • 1≤Q≤100\,000

  • 1 \le s_i \le e_i \le N


출력

모든 질문의 답이 “한 명”이 되도록 하는 배치가 존재한다면, 가능한 PS 하는 학생의 최대 수를 출력한다.

불가능하다면 −1을 출력한다


부분문제

번호 점수 조건
#110점

1 \le N \le 100; 1 \le Q \le 100

#220점

1 \le N \le 5000; 1 \le Q \le 5000

#330점

불가능한 상황이 주어지지 않는다.

#440점

추가 제약 조건 없음


예제 #1

20 4
1 10
5 8
6 15
10 20
2

예제 #2

10 3
3 4
6 8
1 10
-1

예제 #3

20 4
3 10
5 8
6 12
10 16
8

예제 #4

3 3
1 2
2 2
2 3
1


출처

USACO 2013 US Open Gold

로그인해야 코드를 작성할 수 있어요.