//和有依赖的背包相似，这个是循环的方案数
#include<iostream>
#include<vector>
using namespace std;
const int N=70,M=32010;
int f[M];
typedef pair<int,int> PII;
vector<PII> sv[N];
PII master[N];
int n,m;
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        int v,p,t;
        scanf("%d%d%d",&v,&p,&t);
        p*=v;
        if(!t)master[i]={v,p};
        else sv[t].push_back({v,p});
    }
    for(int i=1;i<=n;i++)
        for(int u=m;u>=0;u--)
        {
            //买附件等价于买主见，直接选主件买
            for(int j=0;j<1<<sv[i].size();j++)  //所有选择情况
            {
                int v=master[i].first,w=master[i].second;  //主件
                for(int k=0;k<sv[i].size();k++)  
                    if(j>>k&1)   //每一位相当于物品，选择情况
                    {
                        v+=sv[i][k].first;
                        w+=sv[i][k].second;

                        //累加这一类的费用，价值
                    }
                if(u>=v)f[u]=max(f[u],f[u-v]+w);
            }
        }
    printf("%d",f[m]);
}

#include<iostream>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d%d",&v[i],&w[i]);
    for(int i=n;i>=1;i--)   //这里物品倒着放是因为方便输出字典序最小的方案
        for(int j=0;j<=m;j++)   
        {
            f[i][j]=f[i+1][j];
            if(j>=v[i])f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
        }
    int j=m;
    for(int i=1;i<=n;i++)  //由前一个物品更新而来
        if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i])
        {
            cout<<i<<' ';
            j-=v[i];
        }
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
int n,m;
const int mod=1e9+7,N=1010;
int f[N],g[N];  //g存的是到i点的方案数
int main()
{
    scanf("%d%d",&n,&m);
    memset(f,-0x3f,sizeof f);
    f[0]=0;
    g[0]=1;
    int res=0;
    for(int i=0;i<n;i++)
    {
        int v,w;
        scanf("%d%d",&v,&w);
        for(int j=m;j>=v;j--)
        {
            int maxv=max(f[j],f[j-v]+w);
            int cnt=0;
            if(maxv==f[j])cnt+=g[j];          //不选时候的路径可以更新过来
            if(maxv==f[j-v]+w)cnt+=g[j-v];   //选择的时候路径可以更新过来
            g[j]=cnt%mod;
            f[j]=maxv;
            res=max(maxv,res);  //找最优解
        }
    }
    int cnt=0;
    for(int i=0;i<=m;i++)
        if(res==f[i])
            cnt=(cnt+g[i])%mod;
    cout<<cnt<<endl;
}

#include<cstdio>
using namespace std;
int n,m;
const int N=20;
int w[N][N];
int path[N];
int f[N][N];
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&w[i][j]);


    for(int i=1;i<=n;i++)//循环公司
        for(int j=0;j<=m;j++)//体积
            for(int k=0;k<=j;k++)//给这个公司多少设备，k=0就是这个物品不选的情况
                f[i][j]=max(f[i][j],f[i-1][j-k]+w[i][k]);
    printf("%d\n",f[n][m]);
    int v=m;

    //找路径就是相当于找这个最优解里面有哪些物品
    for(int i=n;i;i--)
        for(int j=0;j<=v;j++)   
            if(f[i][v]==f[i-1][v-j]+w[i][j])
            {
                path[i]=j;
                v-=j;
                break;
            }
    for(int i=1;i<=n;i++)printf("%d %d\n",i,path[i]);
}

//二维费用
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100;
int n,m,k;
int f[N][N];
int min(int x,int y)
{
    return x>y?y:x;
}
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    memset(f,0x3f,sizeof f);   //因为取的为最小值，所以不能初始化为正无穷
    f[0][0]=0;
    while(k--)
    {
        int v1,v2,w;
        scanf("%d%d%d",&v1,&v2,&w);

        //因为每个物品只能用一次，用01背包的倒叙写法
        for(int i=n;i>=0;i--)
            for(int j=m;j>=0;j--)//这里的i和j值的是需要多少的氧和氮
                f[i][j]=min(f[i][j],f[max(i-v1,0)][max(j-v2,0)]+w);//当为负值的时候和0等价的
    }
    printf("%d",f[n][m]);
}

//二维费用
#include<cstdio>
using namespace std;
const int N=1010,M=510;
int n,V1,V2;
int f[N][M];
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
    scanf("%d%d%d",&V1,&V2,&n);
    for(int i=0;i<n;i++)
    {
        int v1,v2;
        scanf("%d%d",&v1,&v2);
        for(int j=V1;j>=v1;j--)
            for(int k=V2-1;k>=v2;k--)
                f[j][k]=max(f[j][k],f[j-v1][k-v2]+1);
    }
    printf("%d ",f[V1][V2-1]);
    int k=V2-1;
    while(k>0&&f[V1][k-1]==f[V1][V2-1])k--;
    printf("%d",V2-k);
}

#include<cstdio>
using namespace std;
const int N=3010;
int a[N],b[N];
int n;
int f[N][N];
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
    {
        int smax=1;
        for(int j=1;j<=n;j++)
        {
            f[i][j]=f[i-1][j];
            if(a[i]==b[j])f[i][j]=max(f[i][j],smax);
            if(a[i]>b[j])smax=max(smax,f[i-1][j]+1);   //这个是由于遍历顺序是从前向后，所以这个smax就是代表1~j-1的前i-1的最大值
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)res=max(res,f[n][i]);
    printf("%d",res);
}
//做这种问题把他的全集想好，怎么更新什么的，其他的也不用想太多

//二维费用就是再加一重循环
#include<cstdio>
using namespace std;
const int N=1e2+10;
int f[N][N];
int n, V, M;
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
    scanf("%d%d%d",&n,&V,&M);
    int v,m,w;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d",&v,&m,&w);
        for(int j=V;j>=v;j--)
            for(int k=M;k>=m;k--)
                f[j][k]=max(f[j][k],f[j-v][k-m]+w);
    }
    printf("%d",f[V][M]);
}

#include<cstdio>
using namespace std;
const int N=1010;
int n,m;
int f[N];
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        int v,w,s;
        scanf("%d%d%d",&v,&w,&s);
        if(s==0)
        {
            for(int j=v;j<=m;j++)f[j]=max(f[j],f[j-v]+w);
        }
        else 
        {
            if(s==-1)s=1;   //01背包就是特殊的分组背包

            //二进制优化
            for(int k=1;k<=s;k*=2)
            {
                for(int j=m;j>=k*v;j--)
                    f[j]=max(f[j],f[j-k*v]+k*w);
                s-=k;
            }
            if(s)
            {
                for(int j=m;j>=s*v;j--)
                    f[j]=max(f[j],f[j-s*v]+s*w);
            }
        }
    }
    printf("%d",f[m]);
}

//普通分组背包
#include<cstdio>
using namespace std;
const int N=6010;
int f[N];
int n,m;
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        int v,w,s;
        scanf("%d%d%d",&v,&w,&s);
        for(int j=m;j>=0;j--)
            for(int k=0;k<=s&&k*v<=j;k++)
                f[j]=max(f[j],f[j-k*v]+k*w);
    }
    printf("%d",f[m]);
}