Minimum Cost Paths

문제

Farmer John's pasture can be regarded as an $N\times MN\backslash times\; M$ ($2\le N\le {10}^{9}2\backslash le\; N\backslash le\; 10^9$, $2\le M\le 2\cdot {10}^{5}2\backslash le\; M\backslash le\; 2\backslash cdot\; 10^5$) 2D grid of square "cells" (picture a huge chessboard). The cell at the $xx$-th row from the top and $yy$-th column from the right is denoted by $(x,y)(x,y)$ for each $x\in [1,N],y\in [1,M]x\backslash in\; [1,N],\; y\backslash in\; [1,M]$. Furthermore, for each $y\in [1,M]y\backslash in\; [1,M]$, the $yy$-th column is associated with the cost $c_{y}c\_y$ ($1\le c_y\le {10}^{9}1\backslash le\; c\_y\backslash le\; 10^9$).

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

• If , Bessie may move to the next column (increasing $yy$ by one) for a cost of $x^{2}x^2$.
• If , Bessie may move to the next row (increasing $xx$ by one) for a cost of $c_{y}c\_y$.

Given $QQ$ ($1\le Q\le 2\cdot {10}^{5}1\backslash le\; Q\backslash le\; 2\backslash cdot\; 10^5$) independent queries each of the form $(x_i,y_i)(x\_i,y\_i)$ ($x_i\in [1,N],y_i\in [1,M]x\_i\backslash in\; [1,N],\; y\_i\backslash in\; [1,M]$), compute the minimum possible total cost for Bessie to move from $(1,1)(1,1)$ to $(x_i,y_i)(x\_i,y\_i)$.

입력

The first line contains $NN$ and $MM$.

The second line contains $MM$ space-separated integers $c_1,c_2,\dots ,c_{M}c\_1,c\_2,\backslash ldots,c\_M$.

The third line contains $QQ$.

The last $QQ$ lines each contain two space-separated integers $x_{i}x\_i$ and $y_{i}y\_i$.

출력

$QQ$ 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:

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

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