#include <fstream>
#include <vector>
using namespace std;
#define Nmax 1010
#define Wmax 10011


int v[Nmax], c[Nmax], d[2][Wmax];

int main()
{
    freopen("energii.in", "r", stdin);
    freopen("energii.out", "w", stdout);
    
    int i, j, n, W, s, ln, lv;
    
    scanf("%d %d", &n, &W);
    
    for(s = 0, i = 0; i < n; ++i)
        scanf("%d %d", v + i, c + i);
    
    for(lv = 0, ln = 1, i = 0; i < n; ++i)
    {
        for(j = 1; j < Wmax; ++j)
        {
            d[ln][j] = d[lv][j];
            
            if(v[i] >= j)
            {
                if(c[i] < d[ln][j] || d[ln][j] == 0)
                    d[ln][j] = c[i];
            }
            else if(d[lv][j - v[i]] > 0)
                if(d[ln][j] == 0 ||
                    d[lv][j - v[i]] + c[i] < d[ln][j])
                d[ln][j] = d[lv][j - v[i]] + c[i];
        }
        
        swap(ln, lv);
    }
    
    printf("%d", d[lv][W]);
    
    return 0;
}