P12725 [KOI 2021 Round 2] 累计距离

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

KOI 国是一个由 $N$ 个村庄构成的国家，这些村庄分布在数轴上。其中第 $i$ 个村庄（$1 \leq i \leq N$）位于位置 $x_i$，并有 $a_i$ 名居民。不会有两个不同村庄位于相同的位置。 KOI 国计划召开一场所有国民都要参加的大会。为此，所有人需要前往会议举办地点，所有人前往该地点所需的移动距离之和称为“累计距离”，我们用 $f(x)$ 表示当会议举办地点为 $x$ 时的累计距离。 住在第 $i$ 个村庄的人前往位置为 $x$ 的会议地点时，需要移动的距离为 $|x_i - x|$。由于第 $i$ 个村庄有 $a_i$ 名居民，因此该村居民所需的总移动距离为 $a_i \times |x_i - x|$。 将所有村庄的该值加总，即可得到在位置 $x$ 举办会议时的累计距离： $$ f(x) = \sum_{i=1}^{N} a_i \times |x_i - x| $$ 例如，若村庄的位置为 $x_1 = 1$、$x_2 = 3$、$x_3 = 6$，各村庄的居民数分别为 $a_1 = 2$、$a_2 = 1$、$a_3 = 3$，当会议地点为 $x = 4$ 时，累计距离为： $$ f(4) = 2 \times |1 - 4| + 1 \times |3 - 4| + 3 \times |6 - 4| = 13 $$ KOI 国已经准备了 $Q$ 个会议地点候选位置。第 $j$ 个候选位置（$1 \leq j \leq Q$）为 $q_j$。多个候选位置之间不会重复，但候选位置可能与某个村庄位置相同。 请编写程序，计算每一个候选会议地点 $q_j$ 的累计距离 $f(q_j)$。

第一行包含两个整数 $N$ 和 $Q$，用一个空格隔开。 接下来的 $N$ 行，每行包含两个整数 $a_i$ 和 $x_i$，表示每个村庄的居民人数及其位置。 接下来的 $Q$ 行，每行一个整数 $q_j$，表示一个候选会议地点的位置。

输出 $Q$ 行。第 $j$ 行输出会议地点为 $q_j$ 时的累计距离 $f(q_j)$。

**约束条件** - $1 \leq N \leq 200\,000$ - 对于所有 $i$（$1 \leq i \leq N$），$1 \leq a_i \leq 1\,000$ - 对于所有 $i$，$-10^9 \leq x_i \leq 10^9$ - $1 \leq Q \leq 200\,000$ - 对于所有 $j$，$-10^9 \leq q_j \leq 10^9$ - 对任意 $1 \leq i_1 < i_2 \leq N$，$x_{i_1} \ne x_{i_2}$（村庄位置各不相同） - 对任意 $1 \leq j_1 < j_2 \leq Q$，$q_{j_1} \ne q_{j_2}$（候选位置各不相同） - 所有给定数值均为整数 **子任务** 1. （9 分）$N,Q \leq 5\,000$ 2. （21 分）对所有 $i$，满足 $1 \leq x_i \leq 200\,000$，且对所有 $j$，满足 $1 \leq q_j \leq 200\,000$ 3. （25 分）对所有 $i$，$a_i = 1$ 4. （45 分）无额外约束条件