#include <bits/stdc++.h>
using namespace std;
ifstream f("rucsac.in"); ofstream g("rucsac.out");
int n,gr,w[5010],p[5010],valmax;
int pd[10010][10010];
int main()
{   f>>n>>gr;
    for(int i=1;i<=n;i++) f>>w[i]>>p[i];
    pd[0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=gr;j++)
        {   pd[i][j]=pd[i-1][j];
            if(w[i]<=j) pd[i][j]=max(pd[i][j],pd[i-1][j-w[i]+p[i]]);
        }
    valmax=pd[n][gr];
    g<<pd[n][gr];
    g.close(); return 0;
}