지점 병합

Moloco는 KAIST 도시에 있는 광고 기술 회사이며, 이 도시는 1차원 직선으로 볼 수 있다. Moloco에는 $N$개의 지점이 있고, $i$번째 지점의 영업 구역은 구간 $[l_i, r_i]$이다. 모든 $i$에 대해 $l_i < r_i$이고, $1 \leq i \leq N-1$에 대해 $r_i \leq l_{i+1}$이다.

두 지점의 영업 구역에 모두 포함되는 점이 있으면 두 지점은 교차한다. 예를 들어 $[3, 5]$와 $[5, 7]$은 교차하고, $[1, 4]$와 $[2, 5]$도 교차한다. 하지만 $[1, 2]$와 $[3, 5]$는 교차하지 않는다.

Moloco는 광고비를 써서 지점의 영업 구역을 넓힐 수 있다. Moloco가 $K$원을 쓰면 모든 지점은 영업 구역을 최대 $K$만큼 넓힐 수 있다. 넓어진 영업 구역의 시작점과 끝점은 정수여야 한다.

형식적으로, $i$번째 지점의 새 영업 구역을 $[l_i', r_i']$라고 하자. 다음 조건을 만족해야 한다.

• $l_i' \leq l_i$이고 $r_i \leq r_i'$이다.
• $(l_i - l_i') + (r_i' - r_i) \leq K$이다.
• $l_i'$와 $r_i'$는 모두 정수이다.

지점이 너무 많으면 회사 관리가 어려우므로, Moloco는 모든 지점을 하나로 합치려 한다. 두 지점은 교차하면 합칠 수 있다. 합쳐진 지점의 영업 구역은 두 지점 영업 구역의 합집합이다.

그림 1. $K=4$일 때 첫 번째 예시 상황의 그림

당신은 Moloco에서 일하고 있다. Moloco가 $s$번째부터 $e$번째 지점만 가지고 있다고 가정한 상황을 살펴보려 한다. 각 질의마다, 그 지점들을 모두 하나로 합치는 데 드는 최소 비용을 구하라.

첫 줄에 정수 $N$과 $Q$가 주어진다 ($1 \leq N \leq 5000$, $1 \leq Q \leq 10^6$).

다음 $N$개의 줄에는 각각 정수 $l_i$와 $r_i$가 주어진다 ($1 \leq l_i < r_i \leq 10^9$). 이는 $i$번째 지점의 영업 구역이다. 모든 $1 \leq i \leq N-1$에 대해 $r_i \leq l_{i+1}$이다.

다음 $Q$개의 줄에는 각각 정수 $s_i$와 $e_i$가 주어진다 ($1 \leq s_i \leq e_i \leq N$). 이는 $i$번째 질의이다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 답, 즉 $s_i$번째부터 $e_i$번째 지점을 합치는 최소 비용을 출력한다.

지점이 하나뿐이면 비용이 들지 않는다.