#include<iostream>
using namespace std;

const int N=1010;
int v[N],w[N];
int f[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m]<<endl;
    return 0;
}

题目链接 Acwing 1699.涂色游戏

1699涂色游戏中有个疑问，没有想明白，求助各位大佬。
样例2中，第4行数据：

668232501 586472717 2

上述两个数字互质。
根据格子编号大小，依次手工填色结果如下：
0号格子：红（题目规定0号必定为红）；
586472717号格子：蓝（p2为蓝色）；
668232501号格子：红（p1为红色）；
1172945434号格：蓝（对应586472717*2，p2蓝）
1336465002号格：红（对应668232501*2，p1红）
以此类推，都是红蓝交错涂色，直到公倍数出现，即
391900130449175217号格子：红（公倍数和0号格子地位相同，跟着大数668232501填写，可以做到红蓝交错）
小数蓝，大数红，公倍数选红，可以做到连续涂色数为1，满足k=2的要求
为什么样例中的输出答案是No
(在题目输入中规定p1在前，p2在后，那么当p1>p2时，0号涂红，p2涂蓝，p1涂红，会出现比p2<p1更为有利的方案，可是样例2似乎并没有遵从这一有利方案，认为p1,p2中的小数填红？)

1699涂色游戏中有个疑问，没有想明白，求助各位大佬。
样例2中，第4行数据：

668232501 586472717 2

上述两个数字互质。
根据格子编号大小，依次手工填色结果如下：
0号格子：红（题目规定0号必定为红）；
586472717号格子：蓝（p2为蓝色）；
668232501号格子：红（p1为红色）；
1172945434号格：蓝（对应586472717*2，p2蓝）
1336465002号格：红（对应668232501*2，p1红）
以此类推，都是红蓝交错涂色，直到公倍数出现，即
391900130449175217号格子：红（公倍数和0号格子地位相同，跟着大数668232501填写，可以做到红蓝交错）
小数蓝，大数红，公倍数选红，可以做到连续涂色数为1，满足k=2的要求
为什么样例中的输出答案是No
(在题目输入中规定p1在前，p2在后，那么当p1>p2时，0号涂红，p2涂蓝，p1涂红，会出现比p2<p1更为有利的方案，可是样例2似乎并没有遵从这一有利方案，认为p1,p2中的小数填红？)

#include<iostream>
using namespace std;

const int N=100001;
int stack[N];
int top=0;

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int t;
        cin>>t;
        while(top>0&&stack[top-1]>=t)
            top--;
        if(top==0)
            cout<<"-1 ";
        else
            cout<<stack[top-1]<<" ";
        stack[top++]=t;
    }
    return 0;
}

#include<iostream>
using namespace std;

const int N=100001;
int a[N];
int h=0,t=0;

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        if(s=="push")
        {
            int x;
            cin>>x;
            a[t++]=x;
        }
        else if(s=="pop")
            h++;
        else if(s=="query")
            cout<<a[h]<<endl;
        else
            if(h<t)
                cout<<"NO"<<endl;
            else
                cout<<"YES"<<endl;
    }
    return 0;
}

#include<iostream>
using namespace std;

const int N=100001;
int stack[N],top=0;

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string t;
        cin>>t;
        if(t=="push")
        {
            int x;
            cin>>x;
            stack[top++]=x;
        }
        else if(t=="pop")
            top--;
        else if(t=="empty")
            if(top==0)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        else
            cout<<stack[top-1]<<endl;
    }
    return 0;
}

#include<iostream>
using namespace std;

const int N=100001;
int e[N],L[N],R[N];
int idx=2;

void init()
{
    L[0]=-1,R[0]=1;
    L[1]=0,R[1]=-1;
}
void insert_R(int k,int x)
{
    e[idx]=x;
    L[idx]=k;
    R[idx]=R[k];
    L[R[k]]=idx;
    R[k]=idx;
    idx++;
}
void insert_L(int k,int x)
{
    insert_R(L[k],x);
}
void my_delete(int k)
{
    R[L[k]]=R[k];
    L[R[k]]=L[k];
}
int main()
{
    init();
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        if(s=="L")
        {
            int x;
            cin>>x;
            insert_R(0,x);
        }
        else if(s=="R")
        {
            int x;
            cin>>x;
            insert_L(1,x);
        }
        else if(s=="IL")
        {
            int k,x;
            cin>>k>>x;
            k++;
            insert_L(k,x);
        }
        else if(s=="IR")
        {
            int k,x;
            cin>>k>>x;
            k++;
            insert_R(k,x);
        }
        else
        {
            int k;
            cin>>k;
            k++;
            my_delete(k);
        }
    }
    int p=R[0];
    while(R[p]!=-1)
    {
        cout<<e[p]<<" ";
        p=R[p];
    }
    return 0;
}

#include<iostream>
using namespace std;

const int N=100001;
int e[N],ne[N];
int head=-1;
int idx=0;

void insert_head(int x)
{
    e[idx]=x;
    ne[idx]=head;
    head=idx++;
}
void insert(int k,int x)
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}
void my_delete(int k)
{
    ne[k]=ne[ne[k]];
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        char t;
        cin>>t;
        if(t=='H')
        {
            int x;
            cin>>x;
            insert_head(x);
        }
        else if(t=='D')
        {
            int k;
            cin>>k;
            if(k==0)
                head=ne[head];
            else
                my_delete(k-1);
        }
        else
        {
            int k,x;
            cin>>k>>x;
            insert(k-1,x);
        }
    }
    int p=head;
    while(p!=-1)
    {
        cout<<e[p]<<" ";
        p=ne[p];
    }
    return 0;
}

#include<iostream>
using namespace std;

const int N=1010;
int f[N],v[N][N],w[N][N],s[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        for(int j=1;j<=s[i];j++)
            cin>>v[i][j]>>w[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=0;j--)
            for(int k=1;k<=s[i];k++)
                if(j>=v[i][k])
                    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
    }
    cout<<f[m]<<endl;
    return 0;
}

#include<iostream>
using namespace std;

const int N=1e6+10;
int f[N];
int v[N],w[N],s[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=0;j--)
            for(int k=1;k<=s[i];k++)
                if(j>=v[i]*k)
                    f[j]=max(f[j],f[j-v[i]*k]+w[i]*k);
    }
    cout<<f[m]<<endl;
    return 0;
}