#include <iostream>
#include <cstdio>

using namespace std;
int c[1002][5002];
int main()
{   int n,a[1002],b[1002],w,i,j;
    FILE *f,*g;
    f=fopen("energii.in","r");
    g=fopen("energii.out","w");
    fscanf(f,"%d%d",&n,&w);
    for(i=1;i<=n;i++)
    fscanf(f,"%d%d",&a[i],&b[i]);
    for(i=0;i<=w;i++) c[0][i]=10001;
    for(i=1;i<=n;i++) c[i][0]=10001;
    for(i=1;i<=n;i++)
        for(j=1;j<=w;j++)
         if(a[i]<j) c[i][j]=c[i-1][j];
         else c[i][j]=min(b[i]-c[i-1][j-a[i]],c[i-1][j]);
   fprintf(g,"%d\n",10001+c[n][w]);
    return 0;
}