#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int v[10010];
pair <int, int> o[5005];
int n,Max,g;

int main(){
    fin>>n>>g;
    for(int i=0;i<n;i++)
        fin>>o[i].first>>o[i].second;
    for(int i=0;i<n;i++){
        for(int j=g;j>=o[i].first;j--){
            v[j]=max(v[j],v[j-o[i].first]+o[i].second);
            Max=max(Max,v[j]);
        }
    }
    fout<<Max;
    return 0;
}