#include <bits/stdc++.h>

using namespace std;

int main() {

    ifstream f("rucsac.in");
    ofstream g("rucsac.out");    

    int n,gre;

    f>>n>>gre;

    int dp[n+1][gre+1];
    vector<pair<int,int>>elemente;
    
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= gre; j++)
            dp[i][j] = 0;

    for(int i = 0 ; i < n; i++) {
        
        int w,p;
        f>>w>>p;
        elemente.push_back(make_pair(w,p));
    }    

    for(int i = 1; i <= n; i++) {
        int greutate_obiect_curent = elemente[i-1].first;
        int valoare_obiect_curent = elemente[i-1].second;

        for(int j = 1; j <= gre; j++) {
            if(greutate_obiect_curent <= j) 
                    dp[i][j] = max(valoare_obiect_curent + dp[i-1][j-greutate_obiect_curent], dp[i-1][j]);
    
            
        }
    }

    g<< dp[n][gre];
}