题目描述
​ 小明路过了商店，发现了商人贴出了“大促销”广告。

​ 大促销内容如下，给定 k ，你可以按照自己的价值将其中 k 件商品价格设置为 1 ，这是最低的价格。

​ 小明非常激动，进入商店将所有商品都挑选了一遍，一共有 n 件商品，每件商品都是孤品，只有一件，价格为 w i元，对小明来说价值为vi ，不难发现，不一定越贵的对小明的价值越高。

​ 小明一共有 m 元，并不需要花完，他想知道在大促销中能获得的最大价值。

输入格式
第一行三个整数 n,m,k;

第二行 n 个整数wi；

第三行 n 个整数 vi.

输出格式
可能的最大价值。

样例数据
输入1

6 5 3
5 4 2 7 4 8
2 3 4 1 2 3
​
输出1

12
​
样例解释

购买第1，2，3，6件物品，其中将1，2，6价格设置为1，需要花费5元，获得最大价值12。


数据规模与约定
对于 20% 的数据，n,k≤10。

对于 40% 的数据，n,m,k≤100.

对于额外 20% 的数据，保证k≥n。

对于100%的数据，1≤n,m,k≤1000,1≤wi≤10 3,1≤vi≤10 9。

#include<bits/stdc++.h>
//#include<Windows.h>
#define int unsigned long long
using namespace std;
int n,m,k;
struct node{
	int v;
	int w;
}a[1005];
struct dp2{
	int su;
	int ku;
}dp[1005][1005];
bool cmp(node x,node y){
	return x.w!=y.w ? x.w>y.w : x.v>y.v;
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i].w;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i].v;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=0;i<=1005;i++){
    	dp[0][i].ku=k;
	}
    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){
        	if(dp[i-1][j-1].ku>0&&a[i].v+dp[i-1][j-1].su>dp[i-1][j].su){
		        dp[i][j].su=a[i].v+dp[i-1][j-1].su;
		        dp[i][j].ku=dp[i-1][j-1].ku-1;
			}
	        else if(j-a[i].w>0){
			    if(a[i].v+dp[i-1][j-a[i].w].su>dp[i-1][j].su){
				    dp[i][j].su=a[i].v+dp[i-1][j-a[i].w].su;
			        dp[i][j].ku=dp[i-1][j-a[i].w].ku;
				}
				else{
				    dp[i][j].su=dp[i-1][j].su;
			        dp[i][j].ku=dp[i-1][j].ku;
				}
			}
			else
			    dp[i][j].su=dp[i-1][j].su;
		        dp[i][j].ku=dp[i-1][j].ku;
        }
    }
//    for(int i=0;i<=n;i++){
//    	for(int j=0;j<=m;j++){
//    		cout<<j<<":"<<dp[i][j].su<<" "<<dp[i][j].ku<<"  ";
//		}
//		cout<<"\n";
//	}
cout<<dp[n][m].su;
	return 0;
}