Alchemy

The masterful alchemist Zalán spends his days toiling away in his laboratory transmuting different types of metals. Zalán knows about $N$ different metals, numbered $1$ through $N$. An ingot of the $i$-th metal is worth $v_i$ dollars. Using his alchemical skills, Zalán is able to transmute $c_i$ ingots of the $i$-th metal into a single ingot of the $(i+1)$-th metal. He has not yet figured out how to transmute the $N$-th metal any further.

Every day, he receives a shipment of ingots from the world renowned metal merchant Ea-nāṣir. Specifically there are $Q$ days and on the $i$-th day, he receives $a_i$ ingots of metal $b_i$. Zalán's laboratory is slightly cramped, so at the end of each day he must sell all ingots he has on hand.

Since Zalán knows the upcoming shipments, he wonders: What is the maximum worth of ingots he can end up with on the $i$-th day after some series of transmutations. Zalán is too busy transmuting metals, so he has asked for your help to write a program to calculate this for him.

Input

The first line contains two space separated integers $N$ and $Q$.

The second line contains $N$ space separated integers $v_1, \dots, v_N$

The third line contains $N - 1$ space separated integers $c_1, \dots, c_{N-1}$

The following $Q$ lines each contain two space separated integers $a_i$ and $b_i$

Output

Output $Q$ lines, each with a single integer: the maximum worth of ingots Zalán could be left with if he starts with $a_i$ ingots of metal $b_i$ on the $i$-th day.

Constraints

• $2 \le N \le 100,000$
• $1 \le Q \le 100,000$
• $1 \le v_i \le 10^9$ for all $1 \le i \le N$
• $1 \le c_i \le 9$ for all $1 \le i < N$
• $1 \le a_i \le 10^9$ and $1 \le b_i \le N$ for all $1 \le i \le Q$

Subtasks

• Subtask 1 (+14%): $N = 2$
• Subtask 2 (+10%): $c_i = 1$ for all $1 \le i < N$
• Subtask 3 (+26%): $N, Q \le 1,000$
• Subtask 4 (+21%): $c_i \ge 2$ for all $1 \le i < N$
• Subtask 5 (+29%): No further constraints.

Notes

If you are using a type sensitive language like C++, Java, or C then make sure to use a 64 bit integer type to avoid integer overflow. 64-bit integer types include long long for C or C++, and long for C# or Java.

If you are using Python and your solution is exceeding the time limit, try selecting Python 3.11 (PyPy 7.3.19) when submitting as this will generally make your code run faster.

Sample Explanations

Sample 1

In this case there are four metals worth $2, $3, $1, $7 respectively, and Zalán will receive shipments of ingots on three days. He can transmute the 1st, 2nd, and 3rd metals at rates of 2:1, 1:1, and 2:1 respectively.

On the first day Zalán receives 3 ingots of metal 1, which he can simply sell giving him a profit of $3 \times 2 = 6$ dollars.

On the second day he receives 11 ingots of metal 2, of which he can transmute 10 ingots into metal 3, and then transmute the 10 ingots of metal 3 into 5 ingots of metal 4. This leaves him with a profit of $1 \times 3 + 5 \times 7 = 38$ dollars.

On the third day he receives 2 ingots of metal 4, which he can sell for a profit of $2 \times 7 = 14$ dollars.