P13521 [KOI 2025 #2] 包

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

商户是在 KOI 市经营商店的一位市民。商户的店里有 $N$ 件商品，其中第 $i$ 件商品的重量为 $A_i$。商户收到了情报，得知小偷“金基范”正觊觎自己的店铺，于是他准备采取措施，将损失降到最低。 小偷金基范计划从店里偷走 $K$ 件商品。但如果商品太重，不仅难以偷窃，被警察抓住的可能性也会变高。因此，小偷金基范会**最小化**他所偷商品的总重量。不过，如果店里的商品总数不足 $K$ 件，小偷金基范会偷走店里所有的商品。 在小偷金基范到达店铺之前，商户会把店里的一些商品装进一个包里带走。之后，小偷金基范会对商户没有带走的那些商品，以上述方式实施盗窃。商户希望通过合理地往包里装商品，来**最大化**小偷金基范最终偷走的商品总重量。 商户的包能承受的重量是有限的。当给定一个最大承重 $C$ 时，请对所有的 $x = 1, 2, \ldots, C$ 回答以下问题： * 在商户能放入包中的商品总重量不超过 $x$ 的条件下，小偷金基范偷走的商品总重量的最大值是多少？

第一行给定 $N, K, C$，由空格分隔。 第二行给定 $N$ 个整数 $A_1, A_2, \ldots, A_N$，由空格分隔。

输出 $C$ 行。第 $i$ 行输出当 $x = i$ 时，小偷金基范偷走的商品总重量的最大值。

### 限制条件 * 所有给定的数都是整数。 * $1 \le K \le N \le 5\,000$ * $1 \le C \le 1\,000\,000$ * 对于所有 $i$ ($1 \le i \le N$)，满足 $1 \le A_i \le 1\,000\,000$ ### 子任务 1. (13 分) $N \le 10, A_i \le 10\,000, C \le 10\,000$ 2. (17 分) $N \le 80, A_i \le 10\,000, C \le 10\,000$ 3. (23 分) $A_i \le 10\,000, C \le 10\,000$ 4. (16 分) $K = 1$ 5. (31 分) 无额外限制条件。