Merging Branches

Moloco is an ad-tech company in KAIST city, which can be modeled as a 1-dimensional line. Moloco has $N$ branches, and the sales territory of the $i$th branch is the range $[l_i, r_i]$. It is known that $l_i < r_i$ for all $i$, and $r_i \leq l_{i+1}$ for $1 \leq i \leq N-1$.

Two branches intersect if some point is included in both branches' sales territories. For example, $[3, 5]$ and $[5, 7]$ intersect, and $[1, 4]$ and $[2, 5]$ intersect. But $[1, 2]$ and $[3, 5]$ do not intersect.

Moloco can widen the sales territory of every branch by spending on advertisement. If Moloco spends $K$ won, then every branch may widen its sales territory by at most $K$ length units. The start and end of each widened territory must be integers.

Formally, let the new sales territory of the $i$th branch be $[l_i', r_i']$. The following conditions must hold.

• $l_i' \leq l_i$ and $r_i \leq r_i'$
• $(l_i - l_i') + (r_i' - r_i) \leq K$
• $l_i'$ and $r_i'$ are both integers

Moloco wants to merge all branches into one, because too many branches make company management difficult. Two branches can be merged if they intersect. The sales territory of the merged branch is the union of the two original territories.

Fig 1. Illustration of the first sample case when $K=4$.

You work for Moloco. You want to examine hypothetical scenarios where Moloco owns only the $s$th through $e$th branches. For each query, find the minimum cost to merge all of those branches into one.

The first line contains two integers $N$ and $Q$ ($1 \leq N \leq 5000$, $1 \leq Q \leq 10^6$).

The next $N$ lines each contain two integers $l_i$ and $r_i$ ($1 \leq l_i < r_i \leq 10^9$), the sales territory of the $i$th branch. It is guaranteed that $r_i \leq l_{i+1}$ for all $1 \leq i \leq N-1$.

The next $Q$ lines each contain two integers $s_i$ and $e_i$ ($1 \leq s_i \leq e_i \leq N$), describing the $i$th query.

Print $Q$ lines. The $i$th line contains the answer to the $i$th query, which is the minimum cost to merge branches $s_i$ through $e_i$.

If there is only one branch, no cost is needed.