题目描述

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

输入格式

第一行包含两个正整数n,m(1<=n,m<=500000)，分别表示亩数和收割次数。 第二行包含n个正整数，其中第i个数为ai，依次表示每亩种植的草的生长能力。 接下来m行，每行包含两个正整数d[i],bi，依次描述每次收割。 数据保证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