## USACO 2021 January Contest, Platinum

## Problem 2. Minimum Cost Paths

Contest has ended.

**Log in to allow submissions in analysis mode**

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$ ($1\le Q\le 2\cdot 10^5$) independent queries each of the form $(x_i,y_i)$ ($x_i\in [1,N], y_i\in [1,M]$), compute the minimum possible total cost for Bessie to move from $(1,1)$ to $(x_i,y_i)$.

#### INPUT FORMAT (input arrives from the terminal / stdin):

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 FORMAT (print output to the terminal / stdout):

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

#### SAMPLE INPUT:

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

#### SAMPLE OUTPUT:

0 1 2 3 4 1 5 11 19 29 2 9 20 35 54 3 13 29 49 69

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

#### SCORING:

- Test cases 1-3 satisfy $N,M\le 2000$.
- Test cases 4-8 satisfy $c_2>c_3>\cdots>c_M$.
- Test cases 9-15 satisfy $N\le 2\cdot 10^5$.
- Test cases 16-20 satisfy no additional constraints.

Problem credits: Benjamin Qi