//https://infoarena.ro/problema/rucsac
#include <bits/stdc++.h>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int d[4][10010];
int main()
{
    int n,gr,i;
    fin>>n>>gr;
    int p[5010],g[5010];
    for(i=1;i<=n;i++)
    {
        fin>>g[i]>>p[i];
    }
    int in=1,sf=2;
    for(i=1;i<=n;i++)
    {
        for(int j=0;j<=gr;j++)
        {
            if(g[i]>j)
            {
                d[sf][j]=d[in][j];
            }
            else
            {
                d[sf][j]=max(d[in][j],d[in][j-g[i]]+p[i]);
//                if(d[i-1][j]>(d[i-1][j-g[i]]+p[i]))
//                    d[i][j]=d[i-1][j];
//                else
//                    d[i][j]=d[i-1][j-g[i]]+p[i];
            }
        }
        int c=sf;
        sf=in;
        in=c;

    }
//    for(i=1;i<=n;i++)
//    {
//        for(int j=1;j<=gr;j++)
//        {
//            cout<<d[i][j]<<" ";
//        }
//        cout<<"\n";
//    }
    fout<<d[in][gr];

    return 0;
}