#include <bits/stdc++.h>

using namespace std;

struct ruc{
    int a;
    int b;
    double med;
};

bool comp(ruc a,ruc b)
{
    return (a.b>a.b);
}

int O[10001];
int main()
{
    int n,p,z,k;
    vector <ruc> ar;
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d %d",&n,&p);
    for (int i=0;i<n;i++)
    {
        scanf("%d %d",&z,&k);
        ruc h;
        h.a = z;
        h.b = k;
        h.med = double(z)/double(k);
        ar.push_back(h);
    }
    O[0] = 0;
    int sum = 0;
    for (int i=0;i<n; i++)
    {
        for (int j = p - ar[i].a; j>=0; j--)
        {
            if (O[j+ar[i].a] < O[j] + ar[i].b)
            {
                O[j+ar[i].a] = O[j] + ar[i].b;
                if (O[j+ar[i].a] > sum)
                    sum = O[j+ar[i].a];
            }
        }
    }
  cout << sum;
return 0;
}