高桥去一个比萨店买比萨。 店里有nn种比萨出售，第ii种的价格为p_ip i ​ 元，美味度为d_id i ​ 。比萨店正在开业酬宾，每购买1个比萨，就可以免费获得一个售价更小的比萨。 于是高桥君重复以下购买比萨的过程： （1）选择一个比萨（假设是第ii种），花费p_ip i ​ 元购买第ii种比萨。 （2）从价格小于p_ip i ​ 元的比萨中选择一个，免费获得这个比萨。 高桥只有KK元，通过合理选择每次购买和免费获得的比萨，他最多可以得到的最大美味度的总和是多少？ 【输入格式】 第1行，两个正整数n,Kn,K

接下来nn行，每行2个正整数p_i,d_ip i ​ ,d i ​ ，表示第ii种比萨的价格和美味度 【输出格式】 1个整数，美味度总和的最大值 【输入输出样例#1】 输入#1 3 64 15 17 5 6 33 39 复制 输出#1 102 复制 【输入输出样例#2】 输入#2 5 94 4 2 12 10 16 7 2 4 9 5 复制 输出#2 276 复制 【输入输出样例#3】 输入#3 8 8587 181 89 133 464 29 2 379 434 86 351 8 103 902 489 1 124 复制 输出#3 1949022 复制 【说明提示】 样例1说明：

高桥购买3次比萨：

第1次购买1个第3种比萨，花费33元，然后还可以免费获得一个第1种比萨，美味度为39+17=5639+17=56

第2次购买1个第2种比萨，花费15元，然后还可以免费获得一个第2种比萨，美味度为17+6=2317+6=23

第3次购买1个第2种比萨，花费15元，然后还可以免费获得一个第2种比萨，美味度为17+6=2317+6=23

总美味度为56+23+23=10256+23+23=102 【数据范围】 用背包ok

#include <bits/stdc++.h>
using namespace std;
int n,k,p[305],d[305],dp[10005],pd[305];
int main()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++)
    {
        cin>>p[i]>>d[i];
    }
    for (int i=1;i<=n;i++)
    {
        pd[i]=d[i];
        for (int j=1;j<=n;j++)
        {
            if (p[i]>p[j])
            {
                pd[i]=max(pd[i],d[i]+d[j]);
            }
        }
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=p[i];j<=k;j++)
        {
            dp[j]=max(dp[j],dp[j-p[i]]+pd[i]);
        }
    }
    int ans=0;
    for (int i=1;i<=k;i++)
    {
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}