题目描述

有一个正整数集合 $S$。

有 $m$ 个操作，每个操作表示把 $S$ 内前 $k$ 大的数减 $1$，若集合大小小于 $k$ 则全局减 $1$。

当一个数变为 $0$ 时它会消失，即从集合中删除。

设操作完成后 $S$ 内数的总和为 $f(S)$。

一开始 $S$ 为空集，有 $n$ 次添加，每次输入 $a,b$，表示加入 $a$ 个 $b$，求每次加入后的 $f(S)$，注意每次不会真的进行 $m$ 次操作。

输入格式

第一行两个正整数 $n,m$，表示添加的个数和操作的个数。

接下来 $m$ 行，一行一个正整数 $k$。

接下来 $n$ 行，一行两个正整数 $a,b$。

输出格式

$n$ 行，每行一个正整数，表示此时的 $f(S)$。

输入输出样例 #1

输入 #1

2 3
1
2
3
2 3
3 1

输出 #1

1
3

输入输出样例 #2

输入 #2

5 4
40
50
40
30
10 7
10 6
10 5
10 4
10 3

输出 #2

30
50
60
70
90

说明/提示

对于所有数据，$1\\le a,b,n,m\\le 2\\times 10^6$，$0\\le k\\le 2\\times 10^6$。

本题采用捆绑测试 + 子任务依赖，你需要通过一个子任务的所有测试点才能得到该子任务的分数。