#include <bits/stdc++.h>
using namespace std;
///dp[i][j]-profitul maxim obtinut din primele i obiecte avand
///suma greutatilor j
///dp[i][j]=max(dp[i-1][j],dp[i-1][j-g[i]]+c[i])
///Recurenta s-ar traduce:avem posibilitatea de a alege profitul maxim obtinut din primele i-1 obiecte
///                       cu greutatea j(inseamnca ca nu luam obiectul i),sau putem alege obiectul i incrementant costul
///Observam ca avem nevoie numai de 2 linii.
///Complexitatea O(n*g)
const int nmax=5001;
const int gmax=10001;
int g[nmax],c[nmax],dp[2][gmax],G,n;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int main()
{
    int L0,L1;
    L0=0;
    L1=1;
    fin>>n>>G;
    for(int i=1;i<=n;i++)
        fin>>g[i]>>c[i];
    dp[L0][g[1]]=c[1];
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=G;j++)///nu trebuie sa depasesca G
            if(j>=g[i])
                dp[L1][j]=max(dp[L0][j],dp[L0][j-g[i]]+c[i]);
        else dp[L1][j]=dp[L0][j];
        L0=1-L0;
        L1=1-L1;
    }
    int mx=-1;
    for(int i=1;i<=G;i++)
        mx=max(mx,dp[L0][i]);
    fout<<mx<<"\n";
    fin.close();
    fout.close();
    return 0;
}