28056번 - Merging Branches 서브태스크다국어

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

Moloco defines two branches to intersect if there exists a point which is included in both branches' sales territory. For example $[3, 5]$ and $[5, 7]$ intersect, $[1, 4]$ and $[2, 5]$ intersect while $[1, 2]$ and $[3, 5]$ does not.

Moloco can widen the whole branch's sales territory by efficient advertisement. If Moloco spends $K$ won, then every branch may widen its sales territory by at most $K$ length units. Start and end of widened sales territory should have integer value.

Formally, let the new sales territory of $i$th branch be $[l_i', r_i']$. Below conditions should satisfy.

• $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.

Since too many branches cause difficulty in company management, Moloco is trying to merge all branches into one. Two branch can be merged if they intersect. The sales territory of the new branch will be the union of sales territories of two branches.

Fig 1. Illustration of sample 1 when $K=4$

You are employed to Moloco. You are curious of hypothetical scenarios when Moloco only owns $s$th to $e$th branches. For each of these scenarios, you want to find the minimum cost to merge the branches owned by Moloco. Given $Q$ queries where Moloco only owns $s$th to $e$th branches, solve the minimum cost to merge all branches into one.

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

$N$ lines follow. $i$-th line contains two integers $l_i$, $r_i$ ($1 \leq l_i < r_i \leq 10^9$), denoting the sales territory of $i$th branch. Additionaly, $r_i \leq l_{i+1}$ for all $1 \leq i \leq N-1$.

$Q$ lines follow. $i$-th line contains two integers $s_i$, $e_i$ ($1 \leq s_i \leq e_i \leq N$), denoting the $i$th query.

Print $Q$ lines. On the $i$th line, print the answer to the $i$th query, the minimum cost to merge all branches from $s_i$-th to $e_i$-th.

Notice that you don't need any cost if there is only one branch.