题目描述

注意：本题的时间限制为 3 秒，通常限制的 1.5 倍。本题的内存限制为 512MB，通常限制的 2 倍。

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$），求对于每一个 $k$，Bessie 在回答至少 $k$ 道题目的前提下可以保证的分数。

输入格式

输入的第一行包含 $N$ 和 $Q$。

以下 $N$ 行每行包含 $a_i$ 和 $b_i$。

以下 $Q$ 行每行包含一个 $k$ 的值。每个 $k$ 的值出现至多一次。

输出格式

对于每一个 $k$ 输出一行，包含对于该值的答案。

2 3
3 1
4 2
2
1
0

-3
1
7

提示

样例 1 解释：

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

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