1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int need[510],value[510];
    for (int i=1;i<=n;i++)
        cin>>need[i]>>value[i];
    int f[200020];
    for (int i=0;i<=m;i++) f[i]=0;
    for (int i=1;i<=n;i++)
        for (int v=m;v>=need[i];v--)
            if (f[v]<f[v-need[i]]+value[i])
                f[v]=f[v-need[i]]+value[i];
    int max = 0;
    for (int v=m;v>=0;v--)
        if (max<f[v]) max = f[v];
    cout<<max<<endl;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX