题目描述

自从小 Kalle 赢得了一张刮刮乐的免费洗车券后，他开始以不同的方式看待生活。他开始注意到自己在日常生活中拥有巨大的好运。他最近经历的一些非凡事件包括：因为睡过头而赢得了城市年度懒惰比赛；尽管乘坐最后一班公交车，每天仍能按时到校；以及通过随机选择答案在大学入学考试中获得了 2 分中的 1.4 分。

他现在打算利用他巨大的好运来帮助议会：他计划解决一个臭名昭著的背包问题实例。议会有 $C$ 瑞典克朗的 fika 预算，他们的 fika 供应商有 $N$ 种不同的糖果袋可供选择。每个糖果袋 $i$ 都有一个美味度 $s_i$ 和一个价格 $c_i$ 瑞典克朗。每个糖果袋只能购买一次。目标是购买所有糖果袋的一个子集，使得总花费不超过 $C$，同时最大化总美味度。一般来说，这是一个非常难以解决的问题，但他希望通过利用他的好运来快速解决它。

他的想法如下：首先，取出所有糖果袋并将它们随机排列。然后，忽略前 $K$ 个糖果袋。之后，他将按顺序考虑每个糖果袋，如果买得起就购买，否则就跳过并继续。他会继续这个过程，直到他考虑完所有 $N - K$ 个糖果袋。

如果他选择的顺序足够幸运，某个 $K$ 值将给出最优解。经过大量努力，Kalle 已经改变了所有糖果袋的顺序，他现在请求你帮助他为每个 $K = 0, 1, \dots, N - 1$ 执行他的算法。

输入格式

输入的第一行包含两个整数 $N$ 和 $C$ ($1 \le N \le 2 \cdot 10^5$, $1 \le C \le 10^9$)，分别表示糖果袋的数量和议会的 fika 预算（瑞典克朗）。

输入的第二行包含 $N$ 个整数 $s_1, s_2, \dots, s_N$ ($1 \le s_i \le 10^9$)，表示糖果袋 $i$ 的美味度。

第三行包含 $N$ 个整数 $c_1, c_2, \dots, c_N$ ($1 \le c_i \le 10^9$)，表示糖果袋 $i$ 的价格（瑞典克朗）。

请注意，糖果袋的顺序并非均匀随机选择。

输出格式

输出 $N$ 个以空格分隔的整数，表示 Kalle 的算法找到的糖果袋子集的总美味度，对应于 $K = 0, 1, \dots, N - 1$ 的顺序。

3 15
8 6 10
10 8 6

8 16 10

2 2
1 2
1 2

1 2

提示

子任务

本题采用捆绑测试。 | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | $1$ | $9$| $N \le 1000$ | | $2$ | $12$ | $C \le 50$ | | $3$ | $11$ | 对于所有 $i = 1, 2, \dots, N - 1$，都有 $c_i \le c_{i+1}$。 | | $4$ | $17$ | $c_i$ 在 1 和 $C$ 之间均匀随机选择。 | | $5$ | $51$ | 没有额外限制。 |