题目内容

某公司有一个客户服务队列，队列中共有 $n$ 位客户，按顺序编号为 $1$ 到 $n$，第 $i$ 位客户的服务时长为 $a_i$。

公司计划对队列前 $m$ 位客户进行服务。在此之前，管理员可以劝说一些客户放弃服务并离开队列。每劝离一位客户，公司需要支付固定金额 $k$ 作为补偿。劝离后的客户将立即离队，后面的客户依次补上空位，形成新的队列。最终，公司将为新队列的前 $m$ 位客户提供服务，不会影响 $m$ 位之后的客户。

显然，最终得到服务的前 $m$ 位客户，必定来自原始队列的某个前缀（假设前缀长度为 $p$，$p \ge m$）。在这个前缀中，管理员可以任意选择 $m$ 位客户保留，将其余 $p-m$ 位劝离；前缀之后的客户全部保留且无需劝离。因此，总开销为劝离人数 $(p-m)$ 乘以 $k$，加上所服务的 $m$ 位客户的服务时长之和。

为了最小化总开销，对于确定的 $m$，可以在所有可能的前缀长度 $p$（$m \le p \le n$）中，选择前缀中服务时长最小的 $m$ 位客户保留。你需要对每个 $m = 1, 2, \dots, n$，分别计算从完整初始队列出发的最小总开销。

约束条件：