题目描述

题目译自 PA 2017 Runda 2 Zapiekanki 2

Bajtazar 拥有一家售卖烤三明治的小摊。每天有 $n$ 位顾客光顾他的小摊，第 $i$ 位顾客在时刻 $t_{i}$ 到达（Bajtazar 可以在时刻 $0$ 开始烤制）。每位顾客到达后，会等待直到 Bajtazar 递给他们刚从烤箱中取出的新鲜烤三明治。烤箱一次只能烤制一个三明治，烤制时间总是相同的，且在此期间不能打开烤箱。

Bajtazar 的烤箱已经相当老旧，是时候考虑购买一台新的了。商店里有许多优质烤箱可供选择；对 Bajtazar 来说，设备的关键参数是烤制三明治的时间。当然，Bajtazar 希望购买烤制速度最快的烤箱，但越快的烤箱价格越高，他不确定自己是否负担得起。

Bajtazar 希望顾客等待三明治的总时间尽可能短（他可以在顾客到达前开始烤制，但必须最早在顾客到达时完成烤制——毕竟没人喜欢吃冷的烤三明治）。因此，他决定为不同的烤箱计算这个等待时间，然后再决定购买哪一款。

商店提供了 $m$ 种烤箱，第 $i$ 种烤箱烤制一个三明治的时间为 $d_{i}$。请帮助 Bajtazar，计算如果购买每种烤箱，顾客的等待总时间会是多少。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 200000)$，分别表示顾客数量和烤箱种类数量。

第二行包含 $n$ 个整数 $t_{1}, t_{2}, \ldots, t_{n}$ $(0 \leq t_{1} \leq t_{2} \leq \ldots \leq t_{n} \leq 10^{12})$；数字 $t_{i}$ 表示第 $i$ 位顾客到达小摊的时刻。注意，可能会有两位顾客在同一时刻到达。

第三行包含 $m$ 个整数 $d_{1}, d_{2}, \ldots, d_{m}$ $(1 \leq d_{i} \leq 10^{6})$；数字 $d_{i}$ 表示第 $i$ 种烤箱烤制一个三明治所需的时间。

输出格式

输出应包含恰好 $m$ 行；第 $i$ 行应包含一个整数，表示使用输入中第 $i$ 种烤箱并采用最优烤制策略时，顾客的最小等待总时间。

4 3
3 10 11 23
4 2 5

4
1
6