SP23806 YOSSY - Yossy, The King of IRYUDAT

Yossy 是 IRYUDAT 王国的国王。在他的仁慈与智慧下，王国享有和平的生活。然而，一天敌军突袭，准备摧毁 IRYUDAT。 Yossy 知道此事后，决心保护王国。最合乎逻辑的做法是派遣一支力量至少与敌军匹敌的军队去对抗。军队的力量是每个士兵力量的总和。例如，若有三位士兵，其力量分别是 10、20 和 25，那么这支军队的总力量为 55。 Yossy 集结了所有士兵。为了组成一支强大的军队，他可以选择拥有高力量的士兵，或者将所有士兵派上战场。但由于士兵们都需要食物，而王国目前食物供应不足，他需要在有限的食物条件下，明智地挑选士兵。 麻烦的是，Yossy 并不知道敌军的力量大小。因此，他派手下去计算敌军的实力。他希望列出一个可能的军队力量列表，并按从强到弱排序，这样，一旦知道了敌军力量，他就能迅速派出一支至少同样强大的军队来对抗。需要注意的是，两支军队不同是指士兵的组合不同。

第一行输入一个整数 $n$（$1 < n < 2000$），表示 Yossy 拥有的士兵总数。接下来的 $n$ 行中，每行包含两个整数 $p$（$0 < p < 9999$）和 $f$（$0 < f < 9999$），分别表示每个士兵的力量和所需的食物。然后输入一个整数 $s$（$0 < s < 999999$），代表可提供的最大食物量。最后一行输入一个整数 $k$（$1 < k < 40$），表示 Yossy 列表的长度。如果没有更多可用的士兵组合，列表中剩余的项请输出 0。 对于 $n > 15$ 的测试数据，士兵的力量和食物需求将随机生成，并且不具相关性。

输出 $k$ 行，每行显示一支军队的力量，从最强到第 $k$ 强。 **本翻译由 AI 自动生成**