Bessie 正在参加一场 $N(1\leq N \leq 2 \cdot 10^5)$道判断题的考试. 对于第 $i$ 题，如果她答对了将获得 $a_i$ 分，如果答错将失去 $b_i$ 分，如果不回答则分数不变. $(0 < a_i, b_i \leq 10^9)$ 因为 Bessie 是一头聪明的牛，她知道所有的答案，但她担心 Elsie（主考官）会在测试后追溯性地更改至多 $k$ 道题目，使得 Bessie 无法答对这些题目。 给定 $Q（1\leq Q \leq N+1)$ 个 $k$ 的候选值$（0\leq k \leq N）$，求对于每一个 $k$，Bessie 在回答至少 $k$ 道题目的前提下可以保证的分数.

第一行两个整数 $N,Q$ 以下 $N$ 行每行包含 $a_i,b_i$. 以下 $Q$ 行每行包含一个 $k$ 值.

对于每个 $k$ 输出一个答案.