#P11805. [PA 2017] 烧饼 2

[PA 2017] 烧饼 2

题目背景

译自 PA 2017 R2T1。

题目描述

nn 个人买烧饼。第 ii 个人会在时刻 tit_i 到达。

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

mm 种烤箱,第 ii 种烤箱需要 did_i 单位时间来烤烧饼。也就是说,如果从时刻 aa 开始烤烧饼,那么出炉时间为时刻 (a+di)(a+d_i)

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

输入格式

第一行,两个正整数 n,mn,m

第二行,nn 个非负整数 t1,t2,,tnt_1,t_2,\cdots,t_n

第三行,mm 个正整数 d1,d2,,dmd_1,d_2,\cdots,d_m

输出格式

输出 mm 行,第 ii 行一个非负整数,表示选择第 ii 种烤箱的答案。

4 3
3 10 11 23
4 2 5
4
1
6

提示

  • 1n,m2×1051\le n,m\le 2\times 10^5
  • 0t1t2tn10120\le t_1\le t_2\le \cdots\le t_n\le 10^{12}
  • 1di1061\le d_i\le 10^6