#include <bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int profit1[10001],profit2[10001],greut[5001],pro[5001];
int main()
{
    int n,g,maxim = 0,i,j;
    in>>n >>g;
    for(i=1;i<=n;i++)
        in >>greut[i]>>pro[i];
    for(i=1;i<=n;i++){
        for(j=greut[i];j<=g;j++){
            profit1[j]=max(profit2[j],profit2[j-greut[i]]+pro[i]);
            if(i==n)
                maxim=max(maxim,profit1[j]);
        }
        for(j=1;j<=g;j++)
           profit2[j]=profit1[j];
    }
    out<<maxim;
}