#include <iostream>
#include<fstream>
using namespace std;
int a[5001][10001];
int main()
{
    int g[5001],c[5001],n,gr,i,j;
    ifstream f("rucsac.in");
    ofstream gg("rucsac.out");
    f>>n>>gr;
    for(i=1; i<=n; i++)
        f>>g[i]>>c[i];

    for(i=1; i<=n; i++)
        for(j=1; j<=gr; j++)
            if(j>=g[i])
                a[i][j]=max(c[i]+a[i-1][j-g[i]],a[i-1][j]);
            else
                a[i][j]=a[i-1][j];
gg<<a[n][gr];
    return 0;
}