//动态规划学习记录二----背包问题
//0-1背包:只有一个物品,只能选择选或不选;
//多重背包:每个物品有次数限制;
//完全背包:可以选无限次,也是求最大价值,可以使用2的n次方求解
//具体问题看动态规划dp环节,有详细代码

//采药:https://www.luogu.com.cn/problem/P1048
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,t,w[N],v[N],res,f[N],m;
int main()
{
    cin>>t>>m;
    for(int i=0;i<m;i++) cin>>w[i]>>v[i];
    for(int i=0;i<m;i++)
        for(int j=t;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+v[i]);
    cout<<f[t];
    return 0;
}
//装箱问题:https://www.luogu.com.cn/problem/P1049
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,v[N]={1},w[N],res,f[N];
int main()
{
    cin>>m>>n;
    for(int i=0;i<n;i++) cin>>w[i];
    for(int i=0;i<n;i++)
        for(int j=m;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+w[i]);
    cout<<m-f[m];
    return 0;
}

//宠物小精灵之收服:https://oj.ytu.edu.cn/problem.php?cid=4219&pid=8
//该题类似于精卫填海,建议先食用精卫填海再食用这个:https://www.luogu.com.cn/problem/P1510
#include<bits/stdc++.h>
using namespace std;
const int N=2020;
int m,t,n,f[N][N],w[N],v[N],res;//f要用二维数组来存.分别是精灵球和体力值,算是0-2背包的样子?
int main()
{
    cin>>t>>m>>n;
    for(int i=0;i<n;i++) cin>>w[i]>>v[i];
    for(int i=0;i<n;i++)//这个点就充当一个输送数据的作用
        for(int j=t;j>=w[i];j--)
            for(int k=m;k>=v[i];k--) f[j][k]=max(f[j][k],f[j-w[i]][k-v[i]]+1);//0-1?0-2!
    cout<<f[t][m]<<' ';//这个就是最多的精灵;
    int x=m;//拷贝,x是血量
    while(x>0&&f[t][x-1]==f[t][m]) x--;//当我们的血量大于0并且精灵球等于最大精灵球时,我们的血量要减一下;
    //直到血量为0或者精灵球的数量小于最大精灵量的时候再停止循环,此时的总价值一定是最小的;
    //为什么时f t x-1 ,因为我们要看少一滴血的情况下精灵数是不是还是最大的,所以这里要x-1而不是x

    //为什么要这样统计呢?因为在那个循环里面我们已经将所有的状态全部算出来了,所以说中间是没有空余1状态量的
    //故此时可以用x--来统计
    cout<<m-x; //x可以减少的血量,也就是我们剩余的血量,m-x是被攻击的血量
    return 0;
}

//潜水员:http://ybt.ssoier.cn:8088/problem_show.php?pid=1271
//本题具有思维性,好好思考
//既然要求最小值,那么必然的我们的f数组要全部设为无穷
//不妨思考一下f数组的含义,在以往的题中,f数组代表什么?
//f代表 第i个背包,第j个氧气,第k个氮气的最小重量
//但是你仔细看看你题目要求,你会发现这是一种错误的的状态表示,正确的表示是第i个背包,至少为j个氧气,至少为k个氮气的最小重量

//状态计算：
//不选第 i 个物品：f[i-1,j,k]
//选第 i 个物品：f[i-1,j-vi,k-mi]+wi
//初始化：f[0,0,0] = 0，f[0,j,k]=INF 初始一个都不选，那么氧气含量和氮气含量就是 0，且总重量也是 0。其它由于需要求最小值，所有全部初始化为 INF
//以上两个状态转移和初始化方式，适用于上面两个状态表示…那么肯定是有问题的
//在有问题的状态表示中，状态转移时，f[i-1,j-vi,k-mi]+wi 需要保证 j>=vi,k>=mi，因为不能为负数。体积恰好是负数时的状态是不成立的
//在正确的状态表示中，状态表示的是体积至少是 j，那针对于当前物品的体积大于当前枚举的 j 的时候，该物品仍是可以使用的。
//例如，当前状态 f[2][3] 代表氧气含量至少是 2， 氮气含量至少是 3 的最小气缸重量，同时满足这两个条件才能发生状态转移。
//若现在有一个物品，氧气含量为 3，氮气含量为 2，那么它至少需要 3 的氧气容量， 2 个氮气容量，它也是一种合法状态，只不过现在是多占了一个氧气体积没有使用罢了.
//但是它在该状态定义下确确实实是一种合法状态。所以，如果用该物品的话，状态转移方程为：f[0][1]+w，表示氧气不再需要，再填补至少一个单位的氮气进来就行了。
//故，当氧气或者氮气枚举其体积一方小于 0 的时候，将该状态转移到 0 上去就行了。指其已经不需要再添进来该种气体了

//状态转移方程： f[i,j,k]=min(f[i-1,j,k],f[i-1,max(0,j-vi),max(0,k-mi)]
//优化到二维： f[j][k] = min(f[j][k], f[max(0, j - a)][max(0, k - b)] + w);

//答案：
//氧气含量至少为 n 氮气含量至少为 m 的最小气缸重量 f[n][m]
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,t,f[N][N],w[N],v[N],res=0x3f3f3f,p[N];
int main()
{
    memset(f,0x3f,sizeof f);
    f[0][0]=0;//f[0][0]代表从0个气缸里选，氧气需求为0，氮气需求为0的时候，所携带的气缸的最小重量，很明显是0;
    cin>>m>>t>>n;
    for(int i=0;i<n;i++) cin>>w[i]>>v[i]>>p[i];
    for(int i=0;i<n;i++)
        for(int j=m;j>=0;j--)//为什么枚举到0?
        //不要忘记f数组表示的是什么,f数组表示的是氧气至少为j,氮气至少为k的时候,所以说
        //当我们氧气至少为j的时候,如果j-w[i]<0,那是不是意味着这个罐子的氧气比所需的大,是不是合法的?
        //因为我们是枚举至少所需要的体积,从至少需要0体积一步一步的递增到至少需要m体积
        //所以说我们枚举的时候,不像普通的背包问题那样,背包的容量必须大于物体的体积

        //可以举个更清楚的例子,我们至少需要0个氧气(因为已经有罐子给氧气填满了),1个氮气(那些罐子的氮气少,氧气可能多)
        //那我们的状态是不是这个? -> f[0][1]+w?这就很明了了
            for(int k=t;k>=0;k--) f[j][k]=min(f[j][k],f[max(0,j-w[i])][max(0,k-v[i])]+p[i]);
    cout<<f[m][t];
    return 0;
}

//榨取kkksc03:https://www.luogu.com.cn/problem/P1855
#include<bits/stdc++.h>
using namespace std;
const int N=2020;
int n,m,t,f[N][N],w[N],v[N];
int main()
{
    cin>>n>>m>>t;
    for(int i=0;i<n;i++) cin>>w[i]>>v[i];
    for(int i=0;i<n;i++)
        for(int j=m;j>=w[i];j--)
            for(int k=t;k>=v[i];k--) f[j][k]=max(f[j][k],f[j-w[i]][k-v[i]]+1);
    cout<<f[m][t];
    return 0;
}
//NASA的食物计划:https://www.luogu.com.cn/problem/P1507
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int h,t,n,w[N],v[N],p[N],f[N][N];
int main()
{
    cin>>h>>t>>n;
    for(int i=0;i<n;i++) cin>>w[i]>>v[i]>>p[i];
    for(int i=0;i<n;i++)
        for(int j=h;j>=h[i];j--)
            for(int k=t;k>=v[i];k--) f[j][k]=max(f[j][k],f[j-w[i]][k-v[i]]+p[i]);
    cout<<f[h][t];
    return 0;
}