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