#include <iostream>
#include <fstream>
#define GMAX 1003
#define INF 20003
#define WMAX 5003
using namespace std;

ifstream in("energii.in");
ofstream out("energii.out");

int e[GMAX],c[WMAX],d1[GMAX][WMAX],w,g;

int main()
{
    in >>g >> w;
    for(int i=1;i<=g;i++)
    {
        in >> e[i] >> c[i];
    }

    for(int i=1;i<=g;i++)
    {
        for(int j=1;j<=w;j++)
        {
            d1[i][j] = d1[i-1][j];
            if(j-e[i]>=0)
            {

                if(d1[i-1][j-e[i]]>0 || j-e[i]==0)
                {
                    d1[i][j] = d1[i-1][j-e[i]] + c[i];
                }
            }
        }
    }

//    for(int i=0;i<=g;i++)
//    {
//
//        for(int j=0;j<=w;j++)
//        {
//            cout << d1[i][j] << " " ;
//        }
//        cout << endl;
//    }

    out << d1[g][w];
    return 0;
}