#include <fstream>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int n,a[2][10001],m,x,y;

int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>y>>x;
        for (int j=1;j<=m;j++) {
            if (j>=y) {
                a[2][j]=a[1][j-y]+x;
            }
            if (a[2][j-1]>a[2][j]) {
                a[2][j]=a[2][j-1];
            }
            if (a[1][j]>a[2][j]) {
                a[2][j]=a[1][j];
            }
        }
        for (int j=1;j<=m;j++) {
            a[1][j]=a[2][j];
        }
    }
    cout<<a[1][m];
    return 0;
}