#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n,greutate_max,greutate[5005],valoare[5005],profit[5005][10005];
int main()
{
    cin>>n>>greutate_max;
    for(int i=1;i<=n;i++)
        cin>>greutate[i]>>valoare[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=greutate_max;j++)
            if(greutate[i]>j)
                profit[i][j]=profit[i-1][j];
            else
                profit[i][j]=max(profit[i-1][j],profit[i-1][j-greutate[i]]+valoare[i]);
    cout<<profit[n][greutate_max];
    return 0;
}