#include <fstream>
using namespace std;
int d[2005][10005];
int greu[5005],val[5005];
int main()
{
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    int n,gr,mx=0;
    cin >> n >> gr;
    for(int i=1;i<=n;i++)
        cin >> greu[i] >> val[i];
    for(int i=1;i<=n;i++)
    {
        for(int g=1;g<=gr;g++)
        {
            if(g-greu[i]>=0)
                d[i][g]=max(d[i-1][g-greu[i]]+val[i],d[i-1][g]);
        }
    }
    for(int g=1;g<=gr;g++)
    {
        if(d[n][g]>mx)
            mx=d[n][g];
    }
    cout << mx;
    return 0;
}