礼物

题目描述:

春节联欢会现场发放礼物，一共有N种礼物，每种礼物有若干个，但是每个人只能取1个，每种物品体积为Vi，价值为Wi。

每个人拥有一个体积为M的袋子，可以随意装取每种礼物，但是礼物体积总和不能超过M。

我们假设按顺序拿取礼物时，每个人拿取礼物的方案不能与前面所有人拿取礼物的方案相同的情况下，使价值总和最大。

小虎同学前面有K个人，求解小虎同学可以最多可以获得多大的价值总和，若小虎同学没有拿取的方案则输出-1。

输入格式:

第一行三个正整数：N,M,K;

以后N行，第I+1行为两个正整数:Vi,Wi。

输出格式:

一行一个整数小虎同学拿取礼物的最优值。

样例输入:

3 5 2
3 5
3 6
2 2

样例输出:

6

提示:

【样例解释】：

第1个人取2\3号物品价值总和为8；

第2个人取1\3号物品价值总和为7；

第3个人(即为小虎同学)取2号物品价值总和为6；

(以上每个同学拿取礼物方案互不相同)所以答案为6。

【数据范围】：

对于30%的数据N<=10，M<=100，Vi<=50，Wi<=100,0<=k<=10;

对于100%的数据N<=100,M<=1000,Vi<=100,Wi<=1000,0<=k<=50。

时间限制: 1000ms
空间限制: 128MB

---