06770. USACO·判断题测验 未做

注意：本题的时间限制为 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$ 输出一行，包含对于该值的答案。

【样例解释】

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

• 测试点 5-7：$Q\le 10$，$N\le 2\cdot 10^5$。

• 测试点 7-20：没有额外限制。

【数据规模与约定】

• 测试点 2-4：$N\le 100$。

• 测试点 5-7：$Q\le 10$，$N\le 2\cdot 10^5$。

• 测试点 7-20：没有额外限制。

供题：Benjamin Qi