智乃想考一道完全背包(Hard version)

题号：NC269398
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Easy version与Hard version题目中的题目要求略有区别，请注意区分，通过Hard version的代码稍加修改可通过Easy。

完全背包是一个经典问题，它指的是给你一个容量大小最大为 $M$ 的背包，然后有 $N$ 种物品，每种物品的体积为 $w_i$ ，价值为 $v_i$ ，且每种物品有无限多个。对于每种物品，你都可以任取若干个放入背包。

智乃现在对完全背包有了一个新的限制，假设将这 $N$ 种物品放入背包后，第 $1$ 种物品最终在背包内放了 $a_{1}$ 个，第 $2$ 种物品最终在背包内放了 $a_{2}$ 个...，第 $i$ 种物品最终在背包内放了 $a_{i}$ 。

得到一个完全背包的答案序列 $[a_{1},a_{2},...,a_{N}]$ 。

智乃现在想要让最终的答案序列先单调非降再单调非升，且第 $K$ 个物品在所选物品中成为选择次数最多的物品，即 $a_{1}\leq a_{2}\leq ... \leq a_{K} \geq ...\geq a_{N}$ 成立。

现在智乃想让你对每一个背包容量 $1,2,3,4,...,M$ 确定一个最小的 $K$ ，使得在这个限制条件满足的前提下，智乃的背包能够装下最大价值总和的物品，并求出在该 $K$ 的限制条件下这些物品的价值总和。

输入描述:

第一行输入两个正整数表示物品的数目，背包的容量。

接下来行输入两个正整数表示物品的体积和价值。

输出描述:

第一行输出 $M$ 个非负整数，第 $i$ 个数表示智乃的背包容量为 $i$ ，自己任选一个 $K \in [1,N]$ ，使得限制条件为 $K$ 的情况下，能够装下的最大价值总和是多少。

第二行输出 $M$ 个非负整数，第 $i$ 个数表示智乃的背包容量为 $i$ 时要想使得装下物品的价值总和最大， $K$ 的最小值为多少。

示例1

输入

复制

输出

复制

100 200 300 400 501 600 700 800 900 1002 1100
1 1 1 1 3 1 1 1 1 3 1

说明

除了在背包容量为的时候，令取得到最优解，其他情况均为取更优