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

题号：NC269396
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 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}$ 成立。

现在智乃将会给你这个参数 $K$ ，你并不需要关注这个答案序列具体是多少，请你告诉智乃，在这个限制条件满足的前提下，智乃的背包容量分别为 $1,2,3,4,...,M$ 时能够装下最大价值多少的物品。

第一行输入三个正整数表示物品的数目，背包的容量，限制条件中参数的值。

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

输出一行个非负整数，第个数表示智乃的背包容量为时最大能装下多少价值的物品。

示例1

复制

2 10 2
1 100
9 1

复制

0 0 0 0 0 0 0 0 1 101

由于，必须先至少取一个号物品才能取号物品，故在背包的容积大于时才开始产生答案。