该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述:

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

小Y现在对完全背包有了一个新的限制，假设将这$N$种物品放入背包后,第$1$种物品最终在背包内放了$a_1$个,第$2$种物品最终在背包内放了$a_2$个,第$i$种物品最终在背包内放了$a_i$.

得到一个完全背包的答案序列$[a_1,a_2,...,a_N]$.

小Y现在想要让最终的答案序列先单调非降再单调非升,且第$K$个物品在所选物品中成为选择次数最多的物品，即$a_1≤a_2≤...≤a_K≥...≥a_N$成立.

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

输入格式:

第一行输入三个正整数$N,M,K(1≤K≤N≤2000,1≤M≤500)$表示物品的数目，背包的容量，限制条件中参数$K$的值。

接下来$N$行输入两个正整$w_i,v_i(1≤w_i≤M,1≤v_i≤10^6)$表示物品的体积和价值。

输出格式:

输出$M$个非负整数，第$i$个数表示小Y的背包容量为 $i$时最大能装下多少价值的物品。

输入输出样例:

输入#1:

2 10 2
1 100
9 1

输出#1:

0 0 0 0 0 0 0 0 1 101