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