题目描述

塔尖国是一个由 $N$ 个村庄构成的国家，这些村庄分布在数轴上。其中第 $i$ 个村庄（ $1 \leq i \leq N$ ）位于位置 $x_i$ ，并有 $a_i$ 名居民。不会有两个不同村庄位于相同的位置。

塔尖国计划召开一场所有国民都要参加的大会。为此，所有人需要前往会议举办地点，所有人前往该地点所需的移动距离之和称为“累计距离”，我们用 $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 $$

塔尖国已经准备了 $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,Q \leq 200\,000$ ， $1 \leq a_i \leq 1\,000$ ， $-10^9 \leq x_i \leq 10^9$
对于所有 $j$ ， $-10^9 \leq q_j \leq 10^9$
村庄位置各不相同，候选位置各不相同
所有给定数值均为整数

子任务

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