区块链是一个不断增长的记录列表，称为区块，它们通过密码学链接在一起。每个区块都包含前一个区块的加密哈希、时间戳和交易数据（通常表示为默克尔树）。根据设计，区块链能够抵御数据篡改。它被称为“一种开放的分布式账本，可以高效、可验证且永久地记录双方之间的交易”。

创新集群生产公司（ICPC）最近决定启动一个与区块链、数据挖掘、自动驾驶汽车和深度学习相关的重点研究项目。ICPC 中有 $m$ 名算法工程师和 $m$ 名软件工程师。ICPC 希望将这个新项目分配给 $k$ 对工程师，每一对由一名算法工程师和一名软件工程师组成。每位工程师最多只能被分配到一对中，否则该工程师的工作负荷会过重。

ICPC 共有 $n$ 栋大楼，从左到右依次排列，编号为 $1, 2, \dots, n$。第 $i$ 栋大楼与第 $(i+1)$ 栋大楼之间的距离为 $d_i$。对于每位工程师，我们已知他们所在的大楼以及将他们分配到该项目的成本。

每一对中的两名工程师需要能够定期会面以讨论项目。对于每一对，ICPC 需要支付 $dis$ 美元的交通费用，其中 $dis$ 等于该对中两名工程师所在大楼之间的距离。

ICPC 现在正在寻找一种能够使工程师分配和交通的总成本最小化的方案。请编写一个程序，帮助 ICPC 找到成本最低的分配方案。由于重点项目是 ICPC 最重要的项目类型，项目的细节需要进一步讨论，且 $k$ 的值尚未确定。因此，你需要求出对于每个 $k = 1, 2, \dots, m$ 的最优分配方案。

输入格式

输入仅包含一组数据。

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 800, 1 \le m \le 50\,000$)，分别表示大楼的数量和工程师的数量。第二行包含 $n-1$ 个整数 $d_1, d_2, \dots, d_{n-1}$ ($1 \le d_i \le 10^6$，对于 $1 \le i \le n-1$)，表示相邻大楼之间的距离。

接下来的 $m$ 行中，第 $i$ 行 ($1 \le i \le m$) 包含两个整数 $x_i$ 和 $c_i$ ($1 \le x_i \le n, 1 \le c_i \le 10^8$)，表示第 $i$ 名算法工程师所在的大楼以及将该工程师分配到项目的成本。再接下来的 $m$ 行中，第 $i$ 行 ($1 \le i \le m$) 包含两个整数 $x'_i$ 和 $c'_i$ ($1 \le x'_i \le n, 1 \le c'_i \le 10^8$)，表示第 $i$ 名软件工程师所在的大楼以及将该工程师分配到项目的成本。

输出格式

输出 $m$ 行，其中第 $i$ ($1 \le i \le m$) 行包含一个整数，表示当 $k=i$ 时的最小总成本。

样例

输入 1

4 3
1 1 1
1 1
1 2
4 6
2 1
2 2
3 5

输出 1

3
8
20