P1027晨汐散余香（aroma）

【题目背景】

海上的颠簸终于渐渐平息，服下藿香正气液的 tfbz 也随 Gioush 大队抵达了特西荼亚海边的晨汐港。为了继续深入海域，众人需要趁船队离港前卖出一批即将失去香气的货物，换取接下来航行所需的补给。

【题目描述】

晨汐港接下来共有若干个可供交易的日子。Gioush 大队带来了 $n$ 份香料，每份香料只有一份，其中第 $i$ 份香料能够换得 $w_i$ 枚金币，并会在第 $t_i$ 天结束时完全失去香气。也就是说，这份香料只能在第 $1$ 天至第 $t_i$ 天中的某一天完成交易。

港口每天至多允许 Gioush 大队交易一份香料。一份香料一旦被卖出便不能再次交易，没有在失去香气前卖出的香料也不能带来任何收益。

对于一次询问，tfbz 可以从所有日子中任意选择不超过 $p_i$ 个日子进行交易，这些日子不要求连续。把选出的香料分别安排到一个不晚于其失效时间的交易日，并保证同一天至多交易一份香料，称为一个交易方案。

tfbz 一共准备了 $q$ 次询问。对于每次询问，请你求出所有合法的交易方案中，Gioush 大队最多能够获得多少枚金币。

【输入格式】

从文件 $\textbf{\textit{aroma.in}}$ 中读入数据。

第一行两个正整数 $n,q$，分别表示香料的数量和询问的数量。

接下来 $n$ 行，每行两个正整数 $w_i,t_i$，分别表示第 $i$ 份香料能够换得的金币数和失去香气的时间。

接下来 $q$ 行，每行一个正整数 $p_i$，表示本次询问中最多可以选择的交易日数量。

【输出格式】

输出到文件 $\textbf{\textit{aroma.out}}$ 中。

共 $q$ 行，第 $i$ 行一个整数，表示第 $i$ 次询问中所有合法的交易方案能够获得的最大金币数。

【样例 1 输入】

15 328 136 2410 254 367 1718293

【样例 1 输出】

110218322

【说明/提示】

【样例 1 解释】

当最多选择 $3$ 个交易日时，可以在第 $1$ 天卖出价值为 $8$ 的香料，在第 $2$ 天卖出价值为 $10$ 的香料，并在第 $3$ 天卖出价值为 $4$ 的香料，共获得 $22$ 枚金币。可以证明，不存在收益更高的交易方案。

【样例 2】

见选手目录下的 $\textbf{\textit{aroma/aroma2.in}}$ 和 $\textbf{\textit{aroma/aroma2.ans}}$。

该组样例符合测试点 $5\sim 8$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{aroma/aroma3.in}}$ 和 $\textbf{\textit{aroma/aroma3.ans}}$。

该组样例符合测试点 $9\sim 12$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{aroma/aroma4.in}}$ 和 $\textbf{\textit{aroma/aroma4.ans}}$。

该组样例符合测试点 $13\sim 16$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{aroma/aroma5.in}}$ 和 $\textbf{\textit{aroma/aroma5.ans}}$。

该组样例符合测试点 $17\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证：$1\leq n,q\leq 2\times 10^5$，$1\leq w_i\leq 10^9$，$1\leq t_i,p_i\leq 10^9$。

特殊性质 A：保证所有 $t_i$ 均相等。

特殊性质 B：保证所有 $t_i\geq n$。