Farmer John's pasture can be regarded as an n * m 2D grid of square "cells" (picture a huge chessboard). The cell at the x-th row from the top and y-th column from the right is denoted by (x, y) for each x ∈ [1, n], y ∈ [1, m]. Furthermore, for each y ∈ [1, m], the y-th column is associated with the cost c[y]
(1 ≤ c[y]
≤ 10^9
).
Bessie starts at the cell (1, 1). If she is currently located at the cell (x, y), then she may perform one of the following actions:
If y < m, Bessie may move to the next column (increasing y by one) for a cost of x[2]
.
If x < n, Bessie may move to the next row (increasing x by one) for a cost of c[y]
.
Given q independent queries each of the form (x[i]
, y[i]
) (x[i]
∈ [1, n], y[i]
∈ [1, m]), compute the minimum possible total cost for Bessie to move from (1, 1) to (x[i]
, y[i]
).
The first line contains n and m (2 ≤ n ≤ 10^9
, 2 ≤ m ≤ 2 * 10^5
).
The second line contains m integers c[1]
, c[2]
, ..., c[m]
.
The third line contains q (1 ≤ q ≤ 2 * 10^5
).
The last q lines each contain two space-separated integers x[i]
and y[i]
.
Print q lines, containing the answers for each query.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).
The output in grid format: