21551번 - Вырубка деревьев 서브태스크다국어

Организация <<2Д>> занимается выдачей разрешений на вырубку леса. Ей поступают заявки на вырубку деревьев, расположенных вдоль шоссе. На шоссе расположены $n$ деревьев, $i$-е из них растёт в точке с координатой $x_i$ и имеет высоту $h_i$. Информация про имеющиеся деревья упорядочена так, что выполняется $x_1 < x_2 < \ldots < 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_i - h_i < x_1$, и нельзя валить вправо, если $x_i + h_i > x_n$.

Ситуация из первого примера: сначала второе дерево валят вправо, затем третье влево влево, и наконец, первое валят вправо

В организацию поступили $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$ ($1 \leq n, q \leq 500\,000$).

Каждая из следующих $n$ строк описывает очередное дерево и содержит два целых числа $x_i$, $h_i$ ($1 \leq x_i \leq 10^9$; $1 \leq h_i \leq 10^9$).

Гарантируется, что $x_1 < x_2 < \ldots < x_n$.

Далее следуют $q$ описаний заявок, по одному в строке. Строка $i$ содержит два целых числа $l_i$, $r_i$ ($1 \leq l_i \leq r_i \leq n$).

Для каждой заявки выведите максимальное количество деревьев, которое можно вырубить, не повредив в процессе ни одного дерева.