Юниорская. Отбор олимпиада по информатике 2022 года за 8 класс | Казахстанские олимпиады

Задача A. Фонтан

Новый фонтан состоит из $n$ вертикально выровненных круглых резервуаров с водой, пронумерованных сверху вниз целыми числами, начиная с $1$, как показано ниже:

Каждый резервуар имеет свой диаметр, объем и кран, который может выпускать любое количество воды внутрь резервуара. Всякий раз, когда объем воды превышает вместимость резервуара, лишняя вода выливается из его стенок и стекает в ближайший снизу резервуар имеющий строго больший диаметр, или выливатеся на голову Мансура если такого резервуара нет. Вам необходимо ответить на $q$ запросов следующего вида: под каким номером водоема заканчивается сток, если из крана $r$-го водоема выпустить $v_i$ литров воды? Если в итоге вода выливается на голову Мансура, ответ должен быть $0$.

Формат входного файла

Первая строка ввода содержит два целых числа — $n$ и $q$. Следующие $n$ строк содержат по два целых числа $d_i$ и $c_i$ - диаметр и вместимость $i$-го резервуара. Следующие $q$ строк содержат по два целых числа $r_i$ и $v_i$.

Формат выходного файла

Выведите $q$ строк по одному целому числу в каждой — ответы на вопросы в том порядке, в котором они заданы.

Примеры

Входные данные

6 5
4 10
6 8
3 5
4 14
10 9
4 20
1 25
6 30
5 8
3 13
2 8

Выходные данные

5
0
5
4
2