구간 겹치기

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)가 한 줄에 하나씩 주어진다. (-109 ≤ a < b ≤ 109)

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

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