#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,G,s,Max;
struct {int val,gr;}a[5001],b[5001];
void load(){f>>n>>G; for (int i=1;i<=n;i++) f>>a[i].gr>>a[i].val,s+=a[i].gr;for (int i=1; i<=s; i++) b[i].gr=-1;Max=0,b[0].gr=0;}
void rucsac()
{
    if (s<G){g<<s;}
    else
    {
        for (int i=1;i<=n;i++)for (int j=s;j>=0;j--) if (b[j].gr!=-1 && b[j+a[i].gr].val<b[j].val+a[i].val) b[j+a[i].gr].gr=a[i].gr,b[j+a[i].gr].val=b[j].val+a[i].val;
        while (b[G].gr==-1) G--;
        g<<b[G].val;
    }
}
int main()
{
    load(),rucsac();
    return 0;
}