题目描述

题目来自 USACO 2021 January Contest, Platinum Problem 2. Minimum Cost Paths。

Farmer John 的牧草地可以看作是一个 $N \times M$（$2 \le N \le 10^9$，$2 \le M \le 2 \times 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 \lt M$，Bessie 可以以 $x^2$ 的代价移动到下一列（$y$ 增加一）。
• 如果 $x \lt N$，Bessie 可以以 $c_y$ 的代价移动到下一行（$x$ 增加一）。

给定 $Q$（$1 \le Q \le 2 \times 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, \ldots , c_M$。

第三行包含 $Q$。

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

输出格式

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

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

样例

输入 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

text

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

text

输出以方阵形式表示如下：

数据范围与提示

• 测试点 $1 \sim 3$ 满足 $N, M \le 2000$。
• 测试点 $4 \sim 8$ 满足 $c_2 \gt c_3 \gt \cdots \gt c_M$。
• 测试点 $9 \sim 15$ 满足 $N \le 2 \times 10^5$。
• 测试点 $16 \sim 20$ 没有额外限制。