Minimum Cost Paths
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]).
Input
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].
Output
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++).
Example
The output in 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| *--*--*--*--*