#include <iostream>
#include <stdio.h>
#include <climits>
using namespace std;
FILE *f,*g;
int n,gg;
int a[3][10002];
int w[10002],p[10002];
void citire()
{
    int i;
    fscanf(f,"%d %d",&n,&gg);
    for(i=1;i<=n;i++)
        fscanf(f,"%d %d",&w[i],&p[i]);
}
void dinamic()
{   int i,j,lp=1,lc=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=gg;j++)
        {
            if(j>=w[i])
            {
                if(a[lp][j]>a[lp][j-w[i]]+p[i])
                    a[lc][j]=a[lp][j];
                else
                    a[lc][j]=a[lp][j-w[i]]+p[i];
            }
            else
                  a[lc][j]=a[lp][j];
        }
        lc=1-lc;
        lp=1-lp;
    }
    fprintf(g,"%d",a[lp][gg]);
    cout<<a[1][gg];
}
int main()
{
    f=fopen("rucsac.in","r");
    g=fopen("rucsac.out","w");
    citire();
    dinamic();
    return 0;
}