#include<fstream>
using namespace std;
ifstream f("rucsac.in",ios::in);
ofstream h("rucsac.out",ios::out);
int main()
{
    int n,G,c[100],g[100],i,j,a[100][100],nr;
    f>>n;
    f>>G;
    for(i=1;i<=n;i++)
    f>>g[i]>>c[i];
    for(i=0;i<=n;i++)
    a[i][0]=0;
    for(j=0;j<=G;j++)
    a[0][j]=0;
    for(i=1;i<=n;i++)
    for(j=1;j<=G;j++)
    if(g[i]<=j)
    if(c[i]+a[i-1][j-g[i]]>a[i-1][j])
    a[i][j]=c[i]+a[i-1][j-g[i]];
    else
    a[i][j]=a[i-1][j];
    else
    a[i][j]=a[i-1][j];
    nr=a[n][G];
    h<<nr;
    return 0;}