#include<bits/stdc++.h>
///...................................*****.................................................///
/// Author : Tanvir Ahmed ///
/// Department of Computer Science ///
/// & Engineering ///
/// Comilla University , Bangladesh. ///
///...................................*****.................................................///

/*....................................Values................................................*/
#define inf 1<<30
#define p5 100007
#define p6 1000007
#define PI acos(-1)
#define M 1000000007

/*....................................Functions.............................................*/
#define sqr(x) x*x
#define sc scanf
#define pf printf
#define scin(x) sc("%d",&(x))
#define scin2(x,y) sc("d",&(x),&(y))
#define scin3(x,y,z) sc("d%d",&(x),&(y),&(z))
#define scln(x) sc("%lld",&(x))
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define all(v) v.begin(), v.end()
#define ok cout << "ok" << endl
#define mem(x,y) memset(x,y,sizeof(x))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)

/*...................................Data_Types............................................*/
#define lli long long int
#define ull unsigned long long int
#define pii pair < int, int>
#define pll pair < ll, ll>
#define veci vector<int>
#define vecl vector<long long int>
#define vecp vector< pair<int,int> >
#define mapstrint map< string , int >
#define mapstrstr map< string , string >
#define mapint map< int, int >
#define uset unordered_set
#define umap unordered_map
#define pq priority_queue

#define pb push_back
#define mp make_pair
#define ss stringstream

/*.....................................Loops...............................................*/
#define rep( i , a , b ) for( i=a ; i<b ; i++)
#define rev( i , a , b ) for( i=a ; i>=b ; i--)
#define repx( i ,a,b, x) for( i=a ; i<b ; i+=x)

#define FastRead ios_base::sync_with_stdio(0);cin.tie(0)

//int month[]={31,28,31,30,31,30,31,31,30,31,30,31};
//long power(long int x, long int y){ int temp; if( y == 0) return 1; temp = power(x, y/2); if (y%2 == 0) return temp*temp; else return x*temp*temp; }
/*lli gcd(lli x,lli y)
{
if(x==0) return y;
return gcd(y%x,x);
}*/
/*
int dx[5] = {1, -1, 0, 0 };
int dy[5] = {0, 0, 1, -1};
*/

using namespace std;

lli n,W,profit[5][100005],w[105],val[105];

void knapsack(lli item,int chk)
{
    if(item>n)
        return;
    if(chk == 0)
    {
        for(int i=1; i<=W; i++)
        {
            if(i<w[item])
            {
                profit[1][i] = profit[0][i];
            }
            else if(profit[0][i]<(val[item]+profit[0][i-w[item]]))
                profit[1][i] = val[item]+profit[0][i-w[item]];
            else
                profit[1][i] = profit[0][i];
        }
        knapsack(item+1,1);
    }
    else
    {
        for(int i=1; i<=W; i++)
        {
            if(i<w[item])
            {
                profit[0][i] = profit[1][i];
            }
            else if(profit[1][i]<(val[item]+profit[1][i-w[item]]))
                profit[0][i] = val[item]+profit[1][i-w[item]];
            else
                profit[0][i] = profit[1][i];
        }
        knapsack(item+1,0);
    }
}

int main()
{
    scln(n);
    scln(W);
    for(int i=1; i<=n; i++)
    {
        scln(w[i]);
        scln(val[i]);
    }
    for(int i=0; i<=W; i++)
        profit[0][i] = 0;
    knapsack(1,0);
    if(n%2==1)
        pf("%lld\n",profit[1][W]);
    else
        pf("%lld\n",profit[0][W]);
    return 0;
}


Measured memory_bytes: 1792