Optimized Navigation on a Costed Grid

Farmer John’s pasture is modeled as an \(N\times M\) grid with \(2\le N\le 10^9\) and \(2\le M\le 2\cdot10^5\). The grid cells are indexed as \((x,y)\) for \(x\in [1,N]\) (row number from top) and \(y\in [1,M]\) (column number from left). For each column \(y\), there is a cost \(c_y\) (with \(1\le c_y\le 10^9\)).

Bessie starts at cell \((1,1)\). If she is at cell \((x,y)\), she can perform one of the following moves (provided that the destination is within bounds):

• If \(y<M\), she can move right to \((x,y+1)\) at a cost of \(x^2\) (note that the horizontal cost depends on the current row).
• If \(x<N\), she can move down to \((x+1,y)\) at a cost of \(c_y\) (the cost is determined by the current column).

Given \(Q\) independent queries (\(1\le Q\le 2\cdot10^5\)), each query provides a target cell \((x_i,y_i)\) with \(x_i\in [1,N]\) and \(y_i\in [1,M]\). For each query, compute the minimum total cost required for Bessie to travel from \((1,1)\) to \((x_i,y_i)\).

The cost to reach a cell \((x,y)\) can be described recursively. Define \(dp(x,y)\) as the minimum cost to reach \((x,y)\). Then we have:

[ \begin{cases} dp(1,1)=0,\[1mm] dp(x,1)=dp(x-1,1)+c_1 \quad (x\ge2),\[1mm] dp(1,y)=dp(1,y-1)+1^2 = dp(1,y-1)+1 \quad (y\ge2),\[1mm] dp(x,y)=\min\Bigl{ dp(x,y-1)+x^2,; dp(x-1,y)+c_y \Bigr} \quad (x,y\ge2). \end{cases} ]

Note that although the constraints are large, for the purpose of sample test cases the grid sizes are small. In an actual competition solution one may need advanced techniques (such as Convex Hull Trick or LiChao trees) to handle the full constraints.

inputFormat

The first line contains three integers \(N\), \(M\) and \(Q\) representing the number of rows, columns, and queries respectively.

The second line contains \(M\) integers: \(c_1, c_2, \dots, c_M\) where \(c_y\) is the cost for moving down in column \(y\).

Then \(Q\) lines follow. Each of these lines contains two integers \(x_i\) and \(y_i\) representing a query asking for the minimum cost to reach cell \((x_i,y_i)\).

outputFormat

For each query, output a single integer — the minimum cost required for Bessie to travel from \((1,1)\) to the target cell \((x_i,y_i)\).

sample

3 3 2
3 1 2
2 3
3 3

4
6