¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#3835
Subtarea

PS를 하는 학생들 1s 128MB

Problemas

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

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

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

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

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


Entrada

첫 줄에 정수 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


Salida

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

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


Subtarea

# Puntaje Condición
#110

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

#220

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

#330

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

#440

추가 제약 조건 없음


Ejemplo #1

20 4
1 10
5 8
6 15
10 20
2

Ejemplo #2

10 3
3 4
6 8
1 10
-1

Ejemplo #3

20 4
3 10
5 8
6 12
10 16
8

Ejemplo #4

3 3
1 2
2 2
2 3
1


Fuente

USACO 2013 US Open Gold

Debes iniciar sesión para escribir código.