P7294 [USACO21JAN] Minimum Cost Paths P

Farmer John’s pasture can be viewed as a 2D grid made of an $N \times M$ ($2 \le N \le 10^9, 2 \le M \le 2 \cdot 10^5$) array of square cells (imagine a huge chessboard). For $x \in [1, N], y \in [1, M]$, the cell in the $x$-th row from top to bottom and the $y$-th column from left to right is denoted by $(x, y)$. In addition, for each $y \in [1, M]$, column $y$ has a cost $c_y$ ($1 \le c_y \le 10^9$). Bessie starts at cell $(1, 1)$. If she is currently at cell $(x, y)$, she can perform one of the following actions: - If $y < M$, Bessie can move to the next column (increase $y$ by $1$) at a cost of $x^2$. - If $x < N$, Bessie can move to the next row (increase $x$ by $1$) at a cost of $c_y$. Given $Q$ ($1 \le Q \le 2 \cdot 10^5$) independent queries, each query gives $(x_i, y_i)$ ($x_i \in [1, N], y_i \in [1, M]$). Compute the minimum 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 $c_1, c_2, \ldots, c_M$. The third line contains $Q$. The last $Q$ lines each contain two space-separated integers $x_i$ and $y_i$.

Output $Q$ lines, one for each query, containing the answer. Note that the integer size used in this problem may require 64-bit integers (for example, `long long` in C/C++).

#### Explanation for Sample 1 The output, shown in grid form, is as follows: ``` 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| *--*--*--*--* ``` #### Testdata Properties - Testdata 1-3 satisfy $N, M \le 2000$. - Testdata 4-8 satisfy $c_2 > c_3 > \cdots > c_M$. - Testdata 9-15 satisfy $N \le 2 \cdot 10^5$. - Testdata 16-20 have no additional constraints. Problem by: Benjamin Qi. Translated by ChatGPT 5