题目描述

农夫 Byteasar 买了一片 $n$ 亩的土地，他要在这上面种草。

他在每一亩土地上都种植了一种独一无二的草，其中，第 $i$ 亩土地的草每天会长高 $a_i$ 厘米。

Byteasar 一共会进行 $m$ 次收割，其中第 $i$ 次收割在第 $d_i$ 天，并把所有高度大于等于 $b_i$ 的部分全部割去。

Byteasar 想知道，每次收割得到的草的高度总和是多少，你能帮帮他吗？

输入格式

第一行包含两个正整数 $n,m$，分别表示亩数和收割次数。

第二行包含 $n$ 个正整数，其中第 $i$ 个数为 $a_i$，依次表示每亩种植的草的生长能力。

接下来 $m$ 行，每行包含两个整数 $d_i,b_i$，依次描述每次收割。

输出格式

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

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

6
6
18
0

提示

对于 $100\%$ 的数据，$1\le n,m\le 5\times 10^5$，$1\le a_i\le 10^6$，$1\le d_i\le 10^{12}$，$0\le b_i\le 10^{12}$。

数据保证 $d_1<d_2<...<d_m$，并且任何时刻没有任何一亩草的高度超过 $10^{12}$。