Minimum Cost Paths

Farmer John's pasture can be regarded as an n \times m 2D grid of square cells (like a large chessboard). The cell at the $x$-th row from the top and $y$-th column from the left is denoted by $(x,y)$ for each x \in [1, n], y \in [1, m]. Furthermore, for each y \in [1, m], the $y$-th column is associated with the cost c_y (1 \le c_y \le 10^9).

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

• If y < m, Bessie may move to the next column (increasing $y$ by one) at a cost of $1$.

• If x < n, Bessie may move to the next row (increasing $x$ by one) at a cost of c_y.

You are given $q$ independent queries, each of the form (x_i, y_i) (x_i \in [1, n], y_i \in [1, m]). For each query, compute the minimum possible total cost for Bessie to move from $(1,1)$ to (x_i, y_i).

\InputFileThe first line contains two integers $n$ and $m$ (2 \le n \le 10^9, 2 \le m \le 2 \times 10^5).

The second line contains $m$ integers c_1, c_2, \ldots, c_m (1 \le c_y \le 10^9).

The third line contains $q$ (1 \le q \le 2 \times 10^5).

Each of the next $q$ lines contains two integers x_i and y_i (x_i \in [1, n], y_i \in [1, m]).

\OutputFilePrint $q$ lines. For each query, output a single line containing the answer.

Note: The large size of integers involved may require the use of 64-bit integer types (e.g., long long in C/C++).

\ExamplesThe output in a grid format:

    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|
  *--*--*--*--*