#include <fstream>
const int NMAX=1005;
const int SMAX=1e7+5;
using namespace std;
ifstream in("energii.in");
ofstream out("energii.out");
int n,s;
int v[NMAX],c[NMAX];
int sume[SMAX],cost[SMAX],smax;
int main()
{
    in>>n;
    in>>s;
    for(int i=1;i<=n;i++)
    {
        in>>v[i];
        in>>c[i];
    }
    smax=0;
    sume[0]=1;
    cost[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=smax;j>=0;j--)
        {
            if(sume[j]!=0)
            {
                sume[j+v[i]]=1;
                if(cost[j+v[i]]<cost[j]+c[i])
                    cost[j+v[i]]=cost[j]+c[i];
            }
        }
    }
    return 0;
}