J. Некромант
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в компьютерную игру. В этой игре его персонаж — некромант. Он сражается с $$$n$$$ монстрами, пронумерованными от $$$1$$$ до $$$n$$$. У каждого монстра есть два параметра: здоровье и сила.

Монокарп рассматривает $$$q$$$ сценариев битвы. В каждом сценарии он выбирает некоторый отрезок $$$[l, r]$$$ монстров и вычисляет количество ходов, необходимых для победы над всеми этими монстрами.

Каждый сценарий проходит следующим образом. Сначала Монокарп убивает монстра $$$l$$$ и воскрешает его в качестве зомби (это не считается ходом). Затем на каждом ходу происходит следующее: пусть $$$i$$$ — индекс первого монстра в отрезке $$$[l, r]$$$, который все еще жив. Все зомби атакуют монстра $$$i$$$, уменьшая его здоровье на суммарную силу зомби. После этого, если у монстра $$$i$$$ остается $$$0$$$ или меньше здоровья, он умирает, и Монокарп воскрешает его в качестве зомби.

Когда монстр воскрешается, сила зомби равна силе монстра.

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

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

В первой строке содержатся два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — количество монстров и количество сценариев соответственно.

Во второй строке содержатся $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$), где $$$a_i$$$ — количество очков здоровья $$$i$$$-го монстра.

В третьей строке содержатся $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^4$$$), где $$$b_i$$$ — сила $$$i$$$-го монстра.

Затем следуют $$$q$$$ строк. $$$j$$$-я из них содержит два целых числа $$$l_j$$$ и $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — границы $$$j$$$-го сценария.

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

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

Пример
Входные данные
7 5
4 5 9 9 4 2 4
1 3 3 1 2 3 3
3 5
1 4
6 6
1 7
2 6
Выходные данные
4
10
0
13
7