Problems
정올시는 왼쪽에서 오른쪽으로 쭉 뻗은 직선 도로를 따라 건설된 도시이다.
도로는 수직선으로 표현되며 그 위에 N개의 건물이 있다.
왼쪽부터 i번째 건물은 도로의 [Li, Ri] 구간에 지어져 있으며 서로 겹치지 않는다.
정올시의 여름은 매우 덥다.
정올시의 시장 서현이는 시민들을 위해 햇빛을 피할 수 있게 공사를 준비 중이다.
당연하지만 건물 안에서는 햇빛을 피할 수 있다.
또 건물 끝에 처마를 달면 그 부분 밑에서는 햇빛을 피할 수 있다.
서현이는 총 Q개의 계획을 해보고 있다.
서현이의 i번째 계획은 Si번째 건물부터 Ei번째 건물까지 햇빛을 전혀 받지 않고 이동할 수 있게 처마를 다는 계획이다.
다시 말해, 두 건물 사이의 어떤 점에서도 햇빛을 받지 않도록 처마를 달아야 한다.
하지만 처마를 아무렇게나 달 수는 없다.
한 건물에 달려있는 처마가 너무 무거우면 그만큼 붕괴 위험이 늘어난다.
따라서 서현이는 각 계획을 실행하면서 한 건물에 달아야 하는 처마 길이 합의 최댓값을 최소화 하고 싶다.
한 번 서현이를 도와 계획의 최솟값을 구해보자!
Input
첫 줄에 N과 Q가 주어진다. (1 <= N <= 5000, 1 <= Q <= 1 000 000)
이후 N줄에 걸쳐 Li, Ri가 주어진다. (1 <= Li <= Ri <= 1 000 000 000, Ri <= Li+1)
이후 Q줄에 걸쳐 Si, Ei가 주어진다. (1 <= Si <= Ei <= N)
<Subtask>
#1 (15점) 1 <= N, Q <= 2 000, Li+1 - Ri <= 20
#2 (15점) 1 <= N, Q <= 2 000
#3 (70점) : 추가적인 제한 조건이 없다.
Output
Q줄에 걸쳐 각 계획에서 한 건물에 달아야 하는 처마 길이의 최댓값의 최소를 출력하라.
Example #1
5 2
1 3
5 6
10 15
20 24
28 33
1 5
3 5
4
3
Example #2
7 7
1 3
6 10
14 18
18 19
22 24
28 29
32 40
1 7
3 5
2 6
1 2
4 4
4 7
3 4
3
2
3
2
0
3
0
You must sign in to write code.