Untitled

#include<bits/stdc++.h>
 
using namespace std;
 
typedef pair<int, int> ii;
 
int n;
int m;
vector<ii> a;
vector< vector<int> > f;    //luu gia tri toi uu
// f[i][j] i: goi thu i - j: khoi luong
 
int main(){
    
    cin >> n >> m;
    a.resize(n+1);
    for(int i=1;i<=n;i++) cin >> a[i].first >> a[i].second; // first = WEIGHT, second = VALUE;
    f.resize(n+1, vector<int> (m+1,0));
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j] = f[i-1][j]; // gia su khong chon goi thu i;
            if (j - a[i].first >= 0)    // gia su chon goi thu i va khoi luong con lai > khoi luong goi thu i;
                f[i][j] = max(f[i][j], f[i-1][j-a[i].first] + a[i].second); // cap nhat f[i][j]; 
            // cout << f[i][j] << endl;
        }
    }
    // cout << "Khoi luong lon nhat: ";
    cout << f[n][m] << endl;
    
    return 0;
}