Farmer John's pasture can be regarded as an N×M (2≤N≤10⁹, 2≤M≤2⋅10⁵) 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 cy (1≤c_y≤10⁹).
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₂.
If x<N, Bessie may move to the next row (increasing x by one) for a cost of c_y.
Given Q (1≤Q≤2⋅10⁵) 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.
The second line contains M space-separated integers c1,c2,…,cM.

The third line contains Q.

The last Q lines each contain two space-separated integers xi and yi

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++)

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

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

Test cases 1-3 satisfy N,M≤2000.
Test cases 4-8 satisfy c2>c3>⋯>cM.
Test cases 9-15 satisfy N≤2⋅105.
Test cases 16-20 satisfy no additional constraints.
Problem credits: Benjamin Qi