You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

译自 PA 2017 R2T1。

题目描述

有 $n$ 个人买烧饼。第 $i$ 个人会在时刻 $t_i$ 到达。

顾客只会买新鲜出炉的烧饼。也就是说，第 $i$ 个人拿到的烧饼必须在时刻 $t_i$ 或者之后出炉。

有 $m$ 种烤箱，第 $i$ 种烤箱需要 $d_i$ 单位时间来烤烧饼。也就是说，如果从时刻 $a$ 开始烤烧饼，那么出炉时间为时刻 $(a+d_i)$。

对于每一种烤箱，计算：如果用一台这种烤箱，从 $0$ 时刻起烤烧饼，计算最优策略下顾客等待时间和的最小值。

输入格式

第一行，两个正整数 $n,m$。

第二行，$n$ 个非负整数 $t_1,t_2,\cdots,t_n$。

第三行，$m$ 个正整数 $d_1,d_2,\cdots,d_m$。

输出格式

输出 $m$ 行，第 $i$ 行一个非负整数，表示选择第 $i$ 种烤箱的答案。

4 3
3 10 11 23
4 2 5

4
1
6

提示

• $1\le n,m\le 2\times 10^5$；
• $0\le t_1\le t_2\le \cdots\le t_n\le 10^{12}$；
• $1\le d_i\le 10^6$。