#include <fstream>
using namespace std;
ifstream cin ("rucsac.in");
ofstream cout ("rucsac.out");
struct info {
    int weight ,price;
};
info v [5001];
int rasp [10001];
int main ()
{
    int n,g;
    cin>>n>>g;
    for (int i = 1;i<=n;++i)
        cin>>v[i].weight>>v[i].price;
    for (int j = 1;j<=n;++j)
        for (int i = g-v[j].weight;i>=0;--i)
            rasp[i+v[j].weight] = max (rasp[i + v[j].weight],rasp[i]  + v[j].price);
    for (int i = g;i>=0;--i)
        if (rasp[i])
        {
            cout<<rasp[i];
            return 0;
        }

}