06650. USACO·最小代价路径 未做

Farmer John 的牧草地可以看作是一个 $N\times M$（$2\le N\le 10^9$,

$2\le M\le 2\cdot 10^5$）的正方形方格组成的二维方阵（想象一个巨大的棋盘）。对于 $x\in [1,N],y\in [1,M]$，从上往下第 $x$ 行、从左往右第 $y$ 列的方格记为 $(x,y)$。此外，对于每一个 $y\in [1,M]$，第 $y$ 列拥有一个代价 $c_y$（$1\le c_y\le 10^9$）。

Bessie 从方格 $(1,1)$ 出发。如果她现在位于方格 $(x,y)$，则她可以执行以下操作之一：

• 如果 $y<M$，Bessie 可以以 $x^2$ 的代价移动到下一列（$y$ 增加一）。
• 如果 $x<N$，Bessie 可以以 $c_y$ 的代价移动到下一行（$x$ 增加一）。

给定 $Q$（$1\le Q\le 2\cdot 10^5$）个独立的询问，每个询问给定 $(x_i,y_i)$（$x_i\in [1,N],y_i\in [1,M]$），计算 Bessie 从 $(1,1)$ 移动到 $(x_i,y_i)$ 的最小总代价。

输入的第一行包含 $N$ 和 $M$。

第二行包含 $M$ 个空格分隔的整数 $c_1,c_2,\dots ,c_M$。

第三行包含 $Q$。

最后 $Q$ 行每行包含两个空格分隔的整数 $x_i$ 和 $y_i$。

输出 $Q$ 行，为每个询问的答案。

注意本题计算中所使用的整数大小可能需要使用 64 位整数型（例如，C/C++ 中的 long long）。

【样例解释】

• 测试点 4-8 满足 $c_2>c_3>\cdots >c_M$。

• 测试点 9-15 满足 $N\le 2\cdot 10^5$。

• 测试点 16-20 没有额外限制。

【数据规模与约定】

• 测试点 1-3 满足 $N,M\le 2000$。

• 测试点 4-8 满足 $c_2>c_3>\cdots >c_M$。

• 测试点 9-15 满足 $N\le 2\cdot 10^5$。

• 测试点 16-20 没有额外限制。

供题：Benjamin Qi