#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

int bpSum(vector<int> val, vector<int> wt, int W) {

    int n = val.size() ;
    int mat[n+1][W+1];

    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= W; j++) {
            if (i == 0 || j == 0) {
                mat[i][j] = 0;
            } else if (j <= wt[i-1]) {
                mat[i][j] = mat[i-1][j];
            } else {
                mat[i][j] = max( (val[i] + mat[i-1][j - wt[i]]), mat[i-1][j] );
            }
        }
    }

    return mat[n][W];
}

int main()
{
    int n,x,W;
    vector<int> val, wt;
    //cin>>n >> W;
    ifstream f ("rucsac.in")
    for(int i = 0; i < n; i++) {
        f >> x;
        wt.push_back(x);
        f >> x;
        val.push_back(x);
    }
    f.close();
    /*for(int i = 0; i < n; i++) {
            cout << val[i] << " ";
    }
    cout << endl;
     for(int i = 0; i < n; i++) {
            cout << wt[i] << " ";
    }
    cout << endl;*/
    //cout << bpSum(val,wt,W) << endl;
    ofstream g ("rucsac.out");
    g << bpSum(val,wt,W) << endl;
    g.close();
    return 0;
}