题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

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

题目描述

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)$。

3 1
2 1
1 3
3 6
4

13

4 5
3 -4
1 -10
2 11
4 6
6
-5
1
-12
14

56
84
66
144
116

提示

约束条件

• $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 分）无额外约束条件