第 1 题累计距离 (`cumulativedistance`)

时间限制 1.0 s · 空间限制 256 MB · 105 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 cumulativedistance.in，输出文件 cumulativedistance.out。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

KOI 国是一个由 $N$ 个村庄构成的国家，这些村庄分布在数轴上。其中第 $i$ 个村庄（ $1 \le i \le 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 \le j \le 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)$ 。

输入：

输出：

输入：

输出：

（9 分） $N, Q \le 5000$
（21 分）对所有 $i$ ，满足 $1 \le x_i \le 200\,000$ ，且对所有 $j$ ，满足 $1 \le q_j \le 200\,000$
（25 分）对所有 $i$ ， $a_i = 1$
（45 分）无额外约束条件