#include <bits/stdc++.h>
#define gmax 10001
#define nmax 5001
using namespace std;

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

int d[gmax][2],v[nmax],g[nmax];

int main()
{
    int n,mg,mx=0;
    in>>n>>mg;
    for(int i=1;i<=n;i++) in>>g[i]>>v[i];

    for(int i=1;i<=n;i++)
        for(int j=g[i];j<=mg;j++)
            d[j][i%2]=max(d[j][(i+1)%2],d[j-g[i]][(i+1)%2]+v[i]);

    for(int i=0;i<=mg;i++)
        mx=max(mx,d[i][n%2]);
    out<<mx;

    return 0;
}