#include <bits/stdc++.h>
using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int l1[10005],l2[10005];
int n,gmax,val,greu;
///.first = greutatea, .second = profitul
///mat[i][j] = profitul maxim dintr-o submultime a primelor i obiecte avand greutatea adunata j
int valmax;

int main()
{
    f >> n >> gmax;
    for (int i=1;i<=n;i++) {
        f >> greu >> val;
        for (int j=0;j<=gmax;j++) {
            l2[j] = l1[j]; ///daca nu folosim obiectul i -> solutia va fi cu aceeasi greutate dar din submultimea i-1
            if (j>=v[i].first) {
                l2[j] = max(l2[j],l1[j-greu]+val);
                ///daca greutatea pasului e mai mare decat cea a
                ///obiectului, va exista o solutie si va fi maximul
                ///dintre cea anterioara (in care nu folosim obiectul),
                ///sau cea in care folosim obiectul (caz in care cautam tot in solutia
                ///cu submultimea i-1, dar greutatea j - gr_obiect_i
            }
        }
        for (int j=0;j<=gmax;j++) {
            l1[j]=l2[j];
        }
    }
    for (int j=0;j<=gmax;j++) {
        valmax = max(valmax,l1[j]);
    }
    g << valmax;
    return 0;
}