// "It does not matter how slowly you go as long as you do not stop." - Confucius
#include <bits/stdc++.h>

using namespace std;

/*
author : Roshan_Mehta
motto : Time Management,Consistency,Patience!!
*/

#define int long long

#ifdef Local_Debug

#define debug(x) cout<<#x <<" "<<x<<"  "
#define debug1(a) cout <<#a<<" " <<a << endl
#define debug2(a, b) cout <<#a<<" "<< a << " "<<#b<<" " << b << endl
#define debug3(a, b, c) cout <<#a<<" "<<a << " "<<#b<<" " << b << " "<<#c<<" " << c << endl
#define debug4(a, b, c, d) cout << #a<<" "<<a << " " <<#b<<" "<< b << " "<<#c<<" " << c << " "<<#d<<" "<< d << endl
void show(vector<int> a)
{for (int i = 0; i < a.size(); i++)
{cout << a[i] << " ";}cout << endl;}
void show(vector<vector<int>> a)
{
    for(int i=0;i<a.size();i++)
    {
        for(int j=0;j<a[i].size();j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
}
void printTime(clock_t begin)
{
    printf("%.3lf seconds\n", (double) (clock() - begin) / CLOCKS_PER_SEC);

}
#else
#define debug(x)
#define debug1(x)
#define debug2(x,y)
#define debug3(x,y,z)
#define debug4(x,y,z,a)
void show(vector<int> a){return;}
void show(vector<vector<int>> a){return;}
void printTime()
{return;}
#endif


#define ll long long
#define pb push_back
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mp make_pair
#define f first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rsort(x) sort(x,greater<int> ())
#define rall(x) rbegin(x), rend(x) //useful in sorting
#define endl "\n"
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl
#define gcd __gcd
#define deci(n) fixed << setprecision(n)
#define test() int test_case;cin >> test_case;while (test_case--)
#define loop(i,a,n) for(int i=a;i<n;i++)


typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef pair<int,pi> tri;
typedef pair<pi,int> rtri;
typedef pair<ll, ll> pl;
typedef pair<double, double> pd;
typedef priority_queue<int, vector<int>, greater<int>> minpq;
typedef priority_queue<int> pq;
typedef unordered_map<int,int> umi;
typedef map<int,int> mi;
#define input(n,k) int n,k;cin>>n;cin>>k;vi arr(n,0);loop(i,0,n){cin>>arr[i];}

const int MOD = 1e9 + 7;
const int md=MOD;

int Power(int n, int x) {int ans = 1;while (x > 0) {if (x & 1) ans = (ans * n) % md;
n = (n * n) % md;x = x >> 1;}return ans;}

vl fact, inv;

void inverse(ll n)
{if(n>=inv.size()){ll size=inv.size();size=size==0? 1:size;
inv.resize(n + 1);inv[0] = 1;
for (ll i = size; i <= n; i++)inv[i] = Power(fact[i], md - 2);}}

void factorial(ll n)
{if(n>=fact.size()){ll size=fact.size();size=size==0? 1:size;
fact.resize(n + 1);fact[0] = 1;for (ll i = size; i <= n; i++)
fact[i] = (fact[i - 1] * i) % md;
}}

ll ncr(ll n, ll r) { return (((fact[n] * inv[r]) % md) * inv[n - r]) % md; }

vl SieveOfEratosthenes(int n)
{
    bool prime[n+1];
    memset(prime, true, sizeof(prime));

    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }

    vl ans;
    for (int p=2; p<=n; p++)
       if (prime[p])
          ans.pb(p);
    return ans;
}
ll NcR(int n, int r)
{long long p = 1, k = 1;if (n - r < r)r = n - r;if (r != 0) {while (r) {p *= n;k *= r;
long long m = gcd(p, k);p /= m;k /= m;n--;r--;}
}else p = 1;return p;// cout << p << endl;
}

//********************THE END OF TEMPLATES*******************//

void q1();
void q2();
void q3();
void knapsack();

int32_t main()
{
    clock_t begin = clock();
    fast();
    // test()
    // {

    // }
    knapsack();
    // printf("%.3lf seconds,\n", (double) (clock() - begin) / CLOCKS_PER_SEC);

    return 0;
}
void knapsack()
{
    int n,w;
    cin>>n>>w;
    vpi roshan(n+1);
    for (int i = 1; i < n+1; i++)
    {
        int a,b;
        cin>>a>>b;
        roshan[i].f=a;
        roshan[i].se=b;
    }
    int dp[n+1][w+1];
    // memset(dp,0,(n+1)*(w+1));
    for (int i = 0; i < n+1; i++)
    {
        for (int j = 0; j < w+1; j++)
        {
            dp[i][j]=0;
        }

    }

    for (int i = 1; i < n+1; i++)
    {
        for (int j = 1; j < w+1; j++)
        {
            if(j>=roshan[i].f)
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-roshan[i].f]+roshan[i].se);
            else
            {
                dp[i][j]=dp[i-1][j];
            }

        }

    }
    cout<<dp[n][w]<<endl;
    // for (int i = 0; i < n+1; i++)
    // {
    //     for (int j = 0; j < w+1; j++)
    //     {
    //         cout<<dp[i][j]<<" ";
    //     }
    //     cout<<endl;

    // }



}

void q2()
{
    int n;
    cin>>n;
    vvi roshan(n);
    for (int i = 0; i < n; i++)
    {
        vi temp(3);
        cin>>temp[0]>>temp[1]>>temp[2];
        roshan[i]=temp;
    }
    vector<tri> dp(n);
    dp[0].f=roshan[0][0];
    dp[0].se.f=roshan[0][1];
    dp[0].se.se=roshan[0][2];
    for (int i = 1; i < n; i++)
    {
        dp[i].f=roshan[i][0]+max(dp[i-1].se.f,dp[i-1].se.se);
        dp[i].se.f=roshan[i][1]+max(dp[i-1].f,dp[i-1].se.se);
        dp[i].se.se=roshan[i][2]+max(dp[i-1].se.f,dp[i-1].f);
    }
    cout<<max(dp.back().f,max(dp.back().se.f,dp.back().se.se))<<endl;



}
void q1()
{
    int n,k;
    cin>>n>>k;
    vi arr(n);
    for (int i = 0; i < n; i++)
    {
        cin>>arr[i];
    }
    vi dp(n);
    dp[0]=0;
    for (int i = 1; i < k and i<n; i++)
    {
        dp[i]=abs(arr[0]-arr[i]);
    }
    // dp[1]=abs(arr[0]-arr[1]);
    for (int i = k; i < n; i++)
    {
        // dp[i]=min(dp[i-1]+abs(arr[i]-arr[i-1]),dp[i-2]+abs(arr[i-2]-arr[i]));
        int ans=INT_MAX;
        for (int j = i-k; j < i; j++)
        {
            ans=min(ans,abs(arr[i]-arr[j])+dp[j]);
        }
        dp[i]=ans;

    }
    cout<<dp.back()<<endl;
    show(dp);

}




Measured memory_bytes: 79232