#include<bits/stdc++.h>
using namespace std;
int weigth[1000];
int cost[1000];
int dp[1000][1000];
int cap;
int item;
int knapsack(int i ,int w)
{

    if(i==item+1)
    {

        return 0;
    }
    int p =0,q=0;
    if(dp[i][w]!=0)
    {

        return dp[i][w];
    }
    if(w+weigth[i]<=cap)
    {


            p = cost[i] + knapsack(i+1,w+weigth[i]);

    }
    q= knapsack(i+1,w);
    dp[i][w]= max(p,q);
    return dp[i][w];
}
int main()
{

freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);

    cin>> item >> cap;
//    int w,c;
    for(int i =1; i<=item; i++)
    {

        cin >> weigth[i] >> cost[i];

    }



    cout << knapsack(1,0) << endl;
}