https://codeforces.com/contest/1635/problem/F

x 递增，考虑维护 w。

1.考虑单点匹配，由 w  大的匹配 w  小的。

显然，若 i < j < k ，且 w_j<=w_k, 那么最优的匹配一定不是 (i,k)。

因为(i,k)的值大于 (i,j)。 所以 (j,k)是一个可能选项。

故维护每个点 i，只需要考虑记录i左右边第一个(如果存在的话)满足  w_j<=w_i  的 j，分别记作 L_i  和  R_i

2.区间上最优解。

自然会有疑问：对于一个单点 i，i左右边第一个满足 权重小于 w_i  的点为 L_i  与 R_i，

  但是 i  本身却可以和区间内其他节点构成本区间的最优解呢？

对于询问区间  [Lq,Rq]，如果有带权距离最小的点对 (a,b) ∣ w_a<=w_b ，满足 a < L_b < b.

由于 w_Lb<=w_b, 根据1的讨论，(a, L_b)的值小于(a,b)的值， (a,b)一定不是最优解。矛盾。

对于询问区间  [Lq,Rq]，如果有带权距离最小的点对 (a,b) ∣ w_a>w_b ，满足 a < R_a < b.

由于 w_Ra<=w_a, 类似根据1的讨论， (R_a, b)的值小于(a,b)的值，(a,b)一定不是最优解。矛盾。

综上，我们得到结论：区间内的带权距离最小的点对一定属于那 最多2n 个点对之中。

即答案匹配只能是区间中所有  (L_i,i)和  (i,R_i) 中最小值。

input

5 5

-2 2

0 10

1 1

9 7

12 2

1 3

2 3

1 5

3 5

2 4