T574963 「PA Mashup #2」烧饼

有 $n$ 个人买烧饼。第 $i$ 个人会在时刻 $t_i$ 到达。 顾客只会买新鲜出炉的烧饼。也就是说，第 $i$ 个人拿到的烧饼必须在时刻 $t_i$ 或者之后**出炉**。 有 $m$ 种烤箱，第 $i$ 种烤箱需要 $d_i$ 单位时间来烤烧饼。也就是说，如果从时刻 $a$ 开始烤烧饼，那么出炉时间为时刻 $(a+d_i)$。 对于每一种烤箱，计算：如果用**一台**这种烤箱，从 $0$ 时刻起烤烧饼，计算最优策略下顾客等待时间和的最小值。

无

无

- $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$。