#include <iostream>
#include <cstdio>

using namespace std;

int a[10000],n,g,gr[5000],pr[5000];

void citire()
{
    scanf("%d %d",&n,&g);

    for(int i=1;i<=n;i++)
        scanf("%d %d",&gr[i],&pr[i]);
}

void rez()
{
    a[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=g;j>=gr[i];j--)
            if(a[j-gr[i]]!=0)
                a[j]=max(a[j-gr[i]]+pr[i],a[j]);
    }

    while(a[g]==0)
        g--;
    printf("%d",a[g]-1);
}


int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);

    citire();

    rez();

    return 0;
}