#include<stdio.h>
#define INF 500000000
int v[10001],n,g;
FILE *fin,*fout;


void adauga(int w,int p)
{
    for(int i=g-1;i>=0;i--)
    {
        if(v[i]==INF)
        continue;
        if(i+w>g)
        continue;
        if(v[i]+p>v[i+w] || v[i+w]==INF)
        v[i+w]=v[i]+p;
    }
}

void initializare()
{
    for(int i=1;i<=g;i++)
        v[i]=INF;
}

void citire()
{
    int p,w;
    fin=fopen("rucsac.in","r");
    fscanf(fin,"%d %d",&n,&g);
    initializare();
    for(int i=1;i<=n;i++)
    {
        fscanf(fin,"%d %d",&w,&p);
        adauga(w,p);
    }

    fclose(fin);
}

void afisare()
{
    fout=fopen("rucsac.out","w");
    fprintf(fout,"%d",v[g]);
    fclose(fout);
}

int main()
{
    initializare();
    citire();
    afisare();
    return 0;
}