311272: CF1958J. Necromancer

J. Necromancertime limit per test6 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Monocarp is playing a computer game. In this game, his character is a necromancer. He is fighting $n$ monsters numbered from $1$ to $n$. Each monster has two parameters: health and strength.

Monocarp considers $q$ scenarios of the battle. In each scenario, he chooses some segment $[l, r]$ of monsters and calculates the number of moves it takes to defeat all these monsters.

Each scenario proceeds as follows. First, Monocarp kills monster $l$ and revives it as a zombie (this does not count as a move). Then each move the following happens: let $i$ be the index of the first monster in the segment $[l, r]$ that is still alive. All zombies attack monster $i$, reducing its health by their total strength. After that, if monster $i$ has $0$ or less health, it dies and Monocarp revives it as a zombie.

When the monster is revived, the zombie's strength is equal to the monster's strength.

Help Monocarp for each scenario to calculate how many moves it will take to kill all the monsters in the segment.

Input

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the number of monsters and the number of scenarios, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$), where $a_i$ is the number of health points of the $i$-th monster.

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^4$), where $b_i$ is the strength of the $i$-th monster.

Then $q$ lines follow. The $j$-th of them contains two integers $l_j$ and $r_j$ ($1 \le l_j \le r_j \le n$) — the boundaries of the $j$-th scenario.

Output

For each scenario, print a single integer — the number of moves it will take to kill all the monsters in the segment.

ExampleInput

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

Output

4
10
0
13
7

题目大意：
单卡普正在玩一款电脑游戏，他的角色是一名死灵法师。他正在与编号从1到n的n只怪物战斗。每只怪物都有两个参数：生命值和攻击力。

单卡普考虑了q个战斗场景。在每个场景中，他选择一段怪物[l, r]，并计算击败这些怪物所需的移动次数。

每个场景的进行方式如下。首先，单卡普杀死怪物l，并将其复活为僵尸（这不计算为移动）。然后每个移动发生以下情况：设i为区间[l, r]中仍然存活的第一只怪物的下标。所有僵尸攻击怪物i，减少其生命值，减少量为所有僵尸的总攻击力。在此之后，如果怪物i的生命值为0或更少，它会死亡，单卡普将其复活为僵尸。

当怪物被复活时，僵尸的攻击力等于怪物的攻击力。

帮助单卡普计算每个场景需要多少个移动才能杀死区间内的所有怪物。

输入输出数据格式：
输入：
第一行包含两个整数n和q（1≤n, q≤2∗10^5）——怪物的数量和场景的数量。
第二行包含n个整数a1, a2, …, an（1≤ai≤10^4），其中ai是第i只怪物的生命值。
第三行包含n个整数b1, b2, …, bn（1≤bi≤10^4），其中bi是第i只怪物的攻击力。
然后q行。第j行包含两个整数lj和rj（1≤lj≤rj≤n）——第j个场景的边界。

输出：
对于每个场景，打印一个整数——击败区间内所有怪物所需的移动次数。题目大意： 单卡普正在玩一款电脑游戏，他的角色是一名死灵法师。他正在与编号从1到n的n只怪物战斗。每只怪物都有两个参数：生命值和攻击力。 单卡普考虑了q个战斗场景。在每个场景中，他选择一段怪物[l, r]，并计算击败这些怪物所需的移动次数。 每个场景的进行方式如下。首先，单卡普杀死怪物l，并将其复活为僵尸（这不计算为移动）。然后每个移动发生以下情况：设i为区间[l, r]中仍然存活的第一只怪物的下标。所有僵尸攻击怪物i，减少其生命值，减少量为所有僵尸的总攻击力。在此之后，如果怪物i的生命值为0或更少，它会死亡，单卡普将其复活为僵尸。 当怪物被复活时，僵尸的攻击力等于怪物的攻击力。 帮助单卡普计算每个场景需要多少个移动才能杀死区间内的所有怪物。 输入输出数据格式： 输入： 第一行包含两个整数n和q（1≤n, q≤2∗10^5）——怪物的数量和场景的数量。 第二行包含n个整数a1, a2, …, an（1≤ai≤10^4），其中ai是第i只怪物的生命值。 第三行包含n个整数b1, b2, …, bn（1≤bi≤10^4），其中bi是第i只怪物的攻击力。 然后q行。第j行包含两个整数lj和rj（1≤lj≤rj≤n）——第j个场景的边界。 输出： 对于每个场景，打印一个整数——击败区间内所有怪物所需的移动次数。