A. 签到游戏

传说在上古时代，有一个简单的签到游戏。能通关这个游戏的幸运挑战者，将会收到一份小礼包。

签到游戏是这样的：

出题人有 个不透明的杯子，倒扣在桌面上，排成一列。这些杯子从左到右依次编号为 至 ，第 个杯子里放着 个小球。当然，由于杯子是不透明且倒扣着的，挑战者并不知道 的具体数值。

出题人对于第 个杯子还设置了一个权值 ， 对挑战者公开。

挑战者可以进行无限多轮操作。在一轮操作中，挑战者可以指定介于 与 之间的 ，花费 的代价，获取第 个至第 个杯子里的小球总数，也即获取 的具体数值。其中， 表示 。

挑战者需要达成的目标是：用尽量小的代价，正确地回答出题人，每个杯子里放着多少个小球，也即回答对于 ， 的具体数值。

现在，有 个挑战者依次进行挑战。他们将告知你他们得到的 ，并希望你帮忙求出每个人为保证达成目标所需的最小代价。

经过你的观察，在第 个挑战者挑战前，出题人会在上个挑战者的 基础上，不改变 ，重新随机生成 ，并修改 序列的某个特定位置 为 ，其余不变。

对于第一个挑战者，出题人会在初始序列的基础上修改。

如果你帮所有挑战者算出了正确的答案，他们会送给你一份礼物 —— 100 分。

从标准输入读入数据。

第一行为两个整数 ，分别表示出题人的杯子个数与挑战者个数。

第二行为 个正整数，第 个正整数表示初始时的 。

接下来 行中，第 行两个正整数 ，表示第 个人挑战前出题人修改 序列的位置，与修改后的数值。

输出到标准输出。

输出 行，第 行为一个整数，表示第 个挑战者达成目标所需要的最小代价。

样例输入

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

样例输出

5
6
10
10
12

样例解释

第一个挑战者得到的 ，可以证明，其最优选择之一为 ，最小代价为 。其中 表示一次 的操作。

第二个挑战者得到的 ，可以证明，其最优选择之一为 ，最小代价为 。

对于其他的挑战者不再赘述。

对于所有数据，保证有 ，，，。