Монокарп играет в компьютерную игру. В этой игре его персонаж — некромант. Он сражается с $$$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 54 5 9 9 4 2 41 3 3 1 2 3 33 51 46 61 72 6
4 10 0 13 7
| Kotlin Heroes: Episode 10 |
|---|
| Закончено |
