#include <stdio.h>
#include <string.h>

const char *FI = "energii.in";
const char *FO = "energii.out";
const int INFI = (1 << 30);

int E[1001], P[1001], D[100001];

inline int MIN (int a, int b) { return (a > b) ? b : a; }
inline int MAX (int a, int b) { return (a > b) ? a : b; }

int main(int argc, const char * argv[]) {
    
    freopen (FI, "r", stdin);
    freopen (FO, "w", stdout);
    int G, W = 0;
    scanf( "%d%d", &G, &W);
    
    memset ( D, -1, sizeof (D)), D[0] = 1;
    
    
    for (int i=1; i <= G; ++ i)
        scanf( "%d%d", &E[i], &P[i]);
    
    int Poz = 0;
    
    for (int i=1; i <= G; ++ i) {
        
        for (int j = Poz; j > -1; -- j) {
            
            if (j + E[i] >= W and D[j] > -1) {
                
                D[j + E[i]] = MAX (D[j + E[i]], D[j] + P[i]);
                Poz = MAX ( Poz, j + E[i]);
            }
            
            
        }
    }
    
    int Ans = INFI;
    
    for (int i = G; i <= 100001; ++ i)
        if (D[i] >= G)
            Ans = MIN (D[i],Ans);
    
    
    printf("%d\n",( Ans == INFI ) ? 0 : (Ans - 1));
    return 0;
}