永远というのは、案外退屈なものだ・  ---八意 永琳

月球背面，心怀纯粹的愤怒的纯狐大人创造了一道弹幕墙，想用这些弹幕的魔力改变月之都的物理法则，让永恒不再是永恒 。八意永琳得知了她的邪恶计划，前来阻止，看到眼前的这一幕。永琳立刻使用了 「天呪「アポロ１３」」。灵梦得知了消息，也前来助阵。

纯狐的弹幕墙使用一个由 个整数组成的序列 描述，其中，第 个弹幕的魔力值是 。
对于弹幕墙，灵梦会使用「梦想封印」，每一次选定一个区间 ，满足区间中的魔力值都大于 （即 ），然后将区间中的全部元素减去 （即 ）。「梦想封印」可以无限次的使用，直到全部的魔力值 恰好为 ，才能把纯狐退治。
至于永琳，月之头脑，发动了 次符卡攻击，每次符卡攻击会给定 ，对于 ，使得 ，保证在操作后 保持非负。
灵梦在初始情况时和永琳每次放完符卡后，都会计划退治妖怪。但是因为她懒得自己动手，她只是假设自己上场，所以她的操作不对序列进行永久修改。请你帮助她计算，每一次，她用符卡退治妖怪所需要的最小操作次数。与之形成对比的是，永琳的修改是永久修改，但是灵梦的修改只是她假想的。

雾雨魔理沙也来观战，她觉得情况太复杂了，用魔法工具简化了情况（所以，下文是简化版题意）：
给出由 个整数组成的序列 ，有 次操作：
每次操作指定两个整数 ，保证 ，然后使得 ，保证在操作后 保持非负；更简单地说，就是指定位置减去 然后向外依次减去的数变小直到减去 。该操作实际修改序列。
对于初始状态、及每次操作完成后，你都需要计算，通过以下假想操作，使得所有数变成 的最少次数。
选择任意区间 ，使得 。该假想操作不会实际修改序列。

第一行输入两个整数  代表序列中的元素个数、操作次数。 
第二行输入  个整数  代表序列中的元素。 
此后  行，每行输入两个整数  代表永琳使用的符卡参数。保证在操作后全部元素保持非负。

在第一行上输出一个整数，代表初始情况下灵梦所需要的退治最小操作次数。 
此后  行，第  行输出一个整数，代表永琳第  次操作后，灵梦所需要的最小假想操作次数。

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

4
3
2
2
1
0

初始时，其中一个最优的假想操作方案是：。
第一次永琳操作后数组变为 ，灵梦可以 。
第二次永琳操作后数组变为 。 
第三次永琳操作后数组变为 。 
第四次永琳操作后数组变为 。 
第五次永琳操作后数组变为 。

5 5
11 7 14 17 6
2 2
1 3
2 4
3 3
1 4

21
22
22
20
19
18