#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++)
        {
            d[i][g]=d[i-1][g];
            if(g-greu[i]>=0)
                d[i][g]=max(d[i-1][g-greu[i]]+val[i],d[i-1][g]);
        }
    }
    cout << d[n][gr];
    return 0;
}