Bessie 正在参加一场包含 $N$ 道判断题的考试（$1\le N\le 2\cdot 10^5$）。对于第 $i$ 道题，如果她答对，将获得 $a_i$ 分；如果答错，将扣除 $b_i$ 分；如果不回答，则不得分也不扣分（$0 < a_i, b_i \le 10^9$）。Bessie 是一头聪明的牛，她知道所有题目的正确答案，但她担心 Elsie（考试的监考人）会在考试后追溯性地修改至多 $k$ 道题的答案，使得 Bessie 原本正确的答案变为错误。给定 $Q$（$1\le Q\le N+1$）个候选的 $k$ 值（$0\le k\le N$），请计算在 Bessie 必须回答至少 $k$ 道题的前提下，她能保证获得的得分。

输入格式

第一行包含两个整数 $N$ 和 $Q$。 接下来的 $N$ 行，每行包含 $a_i$ 和 $b_i$。 接下来的 $Q$ 行，每行包含一个 $k$ 值。每个 $k$ 值只会出现一次。

输出格式

对于每个 $k$，输出一行，表示 Bessie 能保证获得的得分。

样例

样例输入 1

2 3
3 1
4 2
2
1
0

样例输出 1

-3
1
7

样例说明 1

对于每个 $k$ 值，Bessie 最优的策略是回答所有题目。

数据范围

• 测试点 2-4：$N\le 100$
• 测试点 5-7：$Q\le 10$，$N\le 2\cdot 10^5$
• 测试点 7-20：无额外限制。