#include <bits/stdc++.h>
#define maxi(a, b) (a > b?a:b)
#define min(a,b)(a<b?a:b)
using namespace std;
int v[5001], gr[5001];
int max1, suma;
int r[10200];
int main()  {
    FILE *fin = fopen("energii.in", "r");
    FILE *fout = fopen("energii.out", "w");
    int n, g;
    int i, j;
    fscanf(fin, "%d%d", &n, &g);
    int gr, v;
    r[0] = 1;
    max1 = 0;
    int s = 0;
    for(i = 1;i <= n;i++)  {
        fscanf(fin, "%d%d", &v, &gr);
        int cj;
        s+=v;
        cj = min(s, g);
      for(j=cj;j>=0;j--)
            if(r[j])
                if(j+v<=g)
                    r[j+v]=maxi(r[j+v],r[j]+gr);
    }
    max1 = INT_MAX;
    for(i = 0;i <= g;i++)
        if(r[i] > g && r[i]<max1)
            max1 = r[i];
    fprintf(fout, "%d", max1 - 1);
    fclose(fin);
    fclose(fout);
    return 0;
}