#include<bits/stdc++.h>
using namespace std;
int c[110],r[110];
int f[110000];
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d%d",&c[i],&r[i]),r[i]-=c[i];
    memset(f,0,sizeof(f)); 
    for(int i=1;i<=n;i++)if(r[i]>0)
    {
       for(int j=c[i];j<=m;j++)
       {
            f[j]=max(f[j],f[j-c[i]]+r[i]);
       }
    }
	int p=m;while(p>0&&f[p]==f[p-1])p--;
    printf("%d\n",f[p]+m-p);
    return 0;
}