[PA2015]Siano

时间限制:30s      空间限制:256MB

题目描述

农夫Byteasar买了一片n亩的土地,他要在这上面种草。
他在每一亩土地上都种植了一种独一无二的草,其中,第i亩土地的草每天会长高a[i]厘米。
Byteasar一共会进行m次收割,其中第i次收割在第d[i]天,并把所有高度大于等于b[i]的部分全部割去。Byteasar想知道,每次收割得到的草的高度总和是多少,你能帮帮他吗?


输入格式

第一行包含两个正整数n,m(1<=n,m<=500000),分别表示亩数和收割次数。
第二行包含n个正整数,其中第i个数为a[i](1<=a[i]<=1000000),依次表示每亩种植的草的生长能力。
接下来m行,每行包含两个正整数d[i],b[i](1<=d[i]<=10^12,0<=b[i]<=10^12),依次描述每次收割。
数据保证d[1]<d[2]<...<d[m],并且任何时刻没有任何一亩草的高度超过10^12。


输出格式

输出m行,每行一个整数,依次回答每次收割能得到的草的高度总和。


样例输入

4 4
1 2 4 3
1 1
2 2
3 0
4 4

样例输出

6
6
18
0

提示

第1天,草的高度分别为1,2,4,3,收割后变为1,1,1,1。
第2天,草的高度分别为2,3,5,4,收割后变为2,2,2,2。
第3天,草的高度分别为3,4,6,5,收割后变为0,0,0,0。
第4天,草的高度分别为1,2,4,3,收割后变为1,2,4,3。


题目来源

By Claris