No.1012 荷物収集

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 115
作問者 : otamay6otamay6 / テスター : sakaki_tohrusakaki_tohru
3 ProblemId : 3597 / 出題時の順位表
問題文最終更新日: 2020-03-13 21:05:08

問題文

数直線上に$N$ 個の荷物が並んでいます、荷物 $i (1 \le i \le N)$ は位置 $x_i$ にあり、重さは $w_i$ です。
荷物を別の位置に運ぶためには、$\vert$ (移動後の位置) - (移動前の位置) $\vert$ $\times$ (荷物の重さ)と等しいコストが必要です。
$Q$ 個の値 $X_1,X_2,\dots,X_Q$ が与えられます。各 $i(1 \le i \le Q)$ に対して、すべての荷物を位置 $X_i $に運ぶための必要最低限の合計コストをそれぞれ求めて1行ごとに出力してください。

入力

$N\ Q$
$x_1\ w_1$
$x_2\ w_2$
$\vdots$
$x_N\ w_N$
$X_1\ X_2\ \dots\ X_Q$

入力は全て整数で与えられる
$1 \le N,Q \le 10^5$
$1 \le x_i \le 10^9$
$ x_i \neq x_{j}\ (i \neq j)$
$1 \le w_i \le 10^4$
$1 \le X_i \le 10^9$
$ X_i \neq X_{j}\ (i \neq j)$

出力

各 $i(1 \le i \le Q)$ に対して、必要最低限の合計コストをそれぞれ1行ごとに出力してください。
最後に改行してください。

サンプル

サンプル1
入力
2 1
1 10
10 4
5
出力
60

位置1にある荷物を位置5に運ぶのに必要なコストは $(5-1) \times 10 = 40$で、位置10にある荷物を位置5に運ぶのに必要なコストは $(10-5) \times 4 = 20$なので
合計でコストが 60 かかります。

サンプル2
入力
3 3
4 3
9 4
10 10
3 9 10
出力
97
25
22

$Q$ 個の答えはそれぞれ独立に求めてください。

サンプル3
入力
1 3
9 4
3 6 10
出力
24
12
4

サンプル4
入力
10 5
659 6670
2020 3864
2086 2170
2782 600
3304 1393
4274 2995
5534 9315
5845 4033
7859 2981
9532 9707
1993 2759 4455 4812 8723
出力
157522286
142876890
118104646
115125838
170268640

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。