题目背景

翻译自 ROI 2021 D2T3。

“2D” 组织负责发放伐木许可证。他们收到了沿公路的伐木申请。

公路上有 $n$ 棵树，其中第 $i$ 棵树生长在坐标为 $x_i$ 的点上，高度为 $h_i$。关于这些树的信息被排序，满足 $x_1 < x_2 < \dots < x_{n-1} < x_n$。

可以按以下方式逐个砍伐树木：将树砍倒，并让它向左或向右倒下。为了防止树木在倒下时受损，它不应碰到距离它自身高度以内的未砍伐的树木。换句话说，如果位于坐标为 $x_i$，高度为 $h_i$ 的树木向右倒下，则不应该存在坐标为 $x_j$ 的未砍伐的树木，使得 $x_i < x_j < x_i + h_i$。如果同一树木向左倒下，则不应存在坐标为 $x_j$ 的未砍伐的树木，使得 $x_i − h_i < x_j < x_i$。

左边界 $x_1$ 处的树木和右边界 $x_n$ 处的树木旁边有重要的建筑物，因此不允许倒掉的树木落在区间 $[x_1, x_n]$ 之外。换句话说，如果 $x_i − h_i < x_1$，坐标为 $x_i$，高度为 $h_i$ 的树木不能向左倒下；如果 $x_i + h_i > x_n$，坐标为 $x_i$，高度为 $h_i$ 的树木不能向右倒下。

题目描述

组织收到了 $q$ 个伐木申请。每个申请由两个数字 $l_i$ 和 $r_i$ 组成，表示申请者希望砍伐第 $l_i$ 到第 $r_i$ 个树木（包括边界）。

在执行申请的过程中，只允许砍伐从 $l_i$ 到 $r_i$ 编号的树木。被砍伐的树木可以倒到 $l_i$ 的左边或 $r_i$ 的右边的区域，但不能超出 $[x_1, x_n]$ 范围，也不允许触碰 $l_i$ 到 $r_i$ 范围之外的其它树木。

对于每个申请，需要计算在不损坏任何树木的情况下可以砍倒的最大树木数量。每个申请都应独立处理（只是申请了，树没有真的被砍掉）。

输入格式

第一行包含两个整数 $n$ 和 $q$。

接下来的 $n$ 行描述每棵树，每行包含两个整数 $x_i$ 和 $h_i$。保证 $x_1 < x_2 < \dots < x_n$。

然后是 $q$ 个伐木申请的描述，每个申请占一行。第i行包含两个整数 $l_i$ 和 $r_i$。

输出格式

对于每个申请，输出可以砍伐的最大树木数量。

3 3
1 3
3 1
4 2
1 1
2 3
1 3

0
2
3

5 3
1 5
3 1
4 2
5 3
6 1
1 5
5 5
1 1

5
1
0

1 1
100 100
1 1

0

提示

样例一最后一个询问可以这样砍：

对于 $100\%$ 的数据，$1 \le n, q \le 500000,1 \le xi, hi \le 10^9,1 \le l_i \le r_i \le n$。