Description

Farmer John’s pasture can be viewed as a 2D grid made of an $N \times M$ ($2 \le N \le 10^9, 2 \le M \le 2 \cdot 10^5$) array of square cells (imagine a huge chessboard). For $x \in [1, N], y \in [1, M]$, the cell in the $x$-th row from top to bottom and the $y$-th column from left to right is denoted by $(x, y)$. In addition, for each $y \in [1, M]$, column $y$ has a cost $c_y$ ($1 \le c_y \le 10^9$).

Bessie starts at cell $(1, 1)$. If she is currently at cell $(x, y)$, she can perform one of the following actions:

• If $y < M$, Bessie can move to the next column (increase $y$ by $1$) at a cost of $x^2$.
• If $x < N$, Bessie can move to the next row (increase $x$ by $1$) at a cost of $c_y$.

Given $Q$ ($1 \le Q \le 2 \cdot 10^5$) independent queries, each query gives $(x_i, y_i)$ ($x_i \in [1, N], y_i \in [1, M]$). Compute the minimum total cost for Bessie to move from $(1, 1)$ to $(x_i, y_i)$.

Input Format

The first line contains $N$ and $M$.

The second line contains $M$ space-separated integers $c_1, c_2, \ldots, c_M$.

The third line contains $Q$.

The last $Q$ lines each contain two space-separated integers $x_i$ and $y_i$.

Output Format

Output $Q$ lines, one for each query, containing the answer.

Note that the integer size used in this problem may require 64-bit integers (for example, long long in C/C++).

5 4
1 100 100 20
20
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 3
2 3
3 3
4 3
5 3
1 4
2 4
3 4
4 4
5 4

0
1
2
3
4
1
5
11
19
29
2
9
20
35
54
3
13
29
49
69

Hint

Explanation for Sample 1

The output, shown in grid form, is as follows:

    1  2  3  4
  *--*--*--*--*
1 | 0| 1| 2| 3|
  *--*--*--*--*
2 | 1| 5| 9|13|
  *--*--*--*--*
3 | 2|11|20|29|
  *--*--*--*--*
4 | 3|19|35|49|
  *--*--*--*--*
5 | 4|29|54|69|
  *--*--*--*--*

Testdata Properties

• Testdata 1-3 satisfy $N, M \le 2000$.
• Testdata 4-8 satisfy $c_2 > c_3 > \cdots > c_M$.
• Testdata 9-15 satisfy $N \le 2 \cdot 10^5$.
• Testdata 16-20 have no additional constraints.

Problem by: Benjamin Qi.

Translated by ChatGPT 5