시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 51 19 17 40.476%

문제

n개의 구간이 주어진다. 하나의 구간은 두 정수 s, e로 표현되며, 이는 수직선 상에서 [s, e]를 모두 덮고 있다는 뜻이다.

다음은 q개의 쿼리가 주어진다. 하나의 쿼리는 두 정수 a, b로 표현되며, 수직선 상에서 [a, b]가 모두 덮어질 수 있도록 하나 이상의 구간을 선택하였을 때의 최소 비용을 출력하라는 뜻이다.

비용은 선택한 구간의 각 길이의 합으로 계산한다. 구간의 길이는 구간이 덮고 있는 정수의 개수다.

입력

첫째 줄에 구간의 개수 n(1 ≤ n ≤ 100), 쿼리의 개수 q(1 ≤ q ≤ 111,222)가 공백을 사이에 두고 주어진다.

다음 n개의 줄에 구간의 정보(s, e)가 한 줄에 하나씩 주어진다. (-109 ≤ s < e ≤ 109)

다음 q개의 줄에 쿼리의 정보(a, b)가 한 줄에 하나씩 주어진다. (-109a < b ≤ 109)

출력

쿼리의 정답을 한 줄에 하나씩 순서대로 출력한다. 불가능할 경우 -1을 출력한다.

예제 입력 1

3 3
1 3
3 10
4 8
1 7
5 11
2 3

예제 출력 1

11
-1
3

1번 쿼리 : 구간 [1, 3], [3, 10]을 선택할 때, 최소 비용이다. 

2번 쿼리 : 주어진 조건에서, 구간 [5, 11]을 완전히 덮을 수 있는 방법은 없다.

3번 쿼리 : 구간 [1, 3]을 선택할 때, 최소 비용이다.

힌트

빠른 입출력을 사용하도록 하자.

출처

University > 한양대 ERICA > Zero One Algorithm Contest 2020 J번