#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PSET(x,y) fixed<<setprecision(y)<<x
#define pb push_back
#define pf push_front
#define mp make_pair
#define pii pair<int,int>
#define pid pair<int,double>
#define vi vector<int>
#define ff first
#define ss second
#define int long long int
#define ull unsigned long long
#define PI 3.14159265
#define SIZE 200010
#define MOD 1000000007
#define BIG 998244353
#define s(t) scanf("%d",&t)
#define p(t) printf("%d\n",t)
#define mii map<int,int>
#define tc int tcs;cin>>tcs;while(tcs--)
#define set_bit __builtin_popcount
#define MSET(table,i) memset(table, i, sizeof(table))
int toint(const string &s) {stringstream ss; ss << s; int x; ss >> x; return x;}
string tostring ( int number ){stringstream ss; ss<< number; return ss.str();}

int power(int x, int y) {
    int r = 1, z = x;
    while (y) {
        if (y & 1)r *= z;
        z *= z; y = y >> 1;
    }
    return r;
}
int powerm(int x, int y, int p) {
    int r = 1;
    while (y) {
        if (y & 1)r = (r * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return r % p;
}
int modinv(int x, int m) {
    return powerm(x, m - 2, m);
}
int logarithm(int a, int b) {
    int x = 0;
    while (a > 1) {
        x++;
        a /= b;
    }
    return x;
}
int max3(int a, int b, int c) {
    return max(a, max(b, c));
}
int min3(int a, int b, int c) {
    return min(a, min(b, c));
}
int fact[500010];
int nCr(int n, int r) {
    int ans = fact[n];
    ans *= modinv(fact[r], BIG);
    ans %= BIG;
    ans *= modinv(fact[n - r], BIG);
    ans %= BIG;
    return ans;
}


int segmin[1000000],segmax[1000000];
void buildmin(int node, int start, int end,int A[])
{
    if(start == end)
    {
        segmin[node] = A[start];
    }
    else
    {
        int mid = (start + end) / 2;
        buildmin(2*node, start, mid,A);
        buildmin(2*node+1, mid+1, end,A);
        segmin[node] = min(segmin[2*node] , segmin[2*node+1]);
    }
}
void buildmax(int start,int end,int id,int pre[]){
    if(start==end){
        segmax[id]=pre[start];
        return;
    }
    int mid=(start+end)/2;
    buildmax(start,mid,id*2,pre);
    buildmax(mid+1,end,id*2+1,pre);
    segmax[id]=max(segmax[id*2],segmax[id*2+1]);
}
int querymin(int id,int start,int end,int l,int r){
    if(start>r || end<l)
        return INT_MAX;
    if(start>=l && end<=r)
        return segmin[id];
    int mid=(start+end)/2;
    return min(querymin(id*2,start,mid,l,r),querymin(id*2+1,mid+1,end,l,r));
}
int querymax(int id,int start,int end,int l,int r){
    if(start>r || end<l)
        return INT_MIN;
    if(start>=l && end<=r)
        return segmax[id];
    int mid=(start+end)/2;
    return max(querymax(id*2,start,mid,l,r),querymax(id*2+1,mid+1,end,l,r));
}
int count(int x)
{
    int count=0;
    while(x%2==0)
    {
        count++;
        x=x/2;
    }
    return count;
}
map<int,vector<int> > adj;
   int ww[100010];
   int vv[100010];
 int n,w;
 
int32_t main()
{
   
    cin>>n>>w;
 
    for(int i=0;i<n;i++)
    {
        cin>>ww[i]>>vv[i];
    }
   int dp[n+1][w+1];
  memset(dp,0,sizeof(dp));
   for(int i=0;i<n;i++)
   {
    for(int j=0;j<=w;j++)
    {
        if(i==0)
        {
            if(j>=ww[i])
            {
                dp[i][j]=vv[i];
            }
            else
            {
                dp[i][j]=0;
            }
            continue;
        }
        dp[i][j]=dp[i-1][j];
        
        if(j >= ww[i] )
        {
            dp[i][j]=max(dp[i][j] ,vv[i] +  dp[i-1][j-ww[i]] );
        }
    }
   }
//   for(int i=0;i<n;i++)
//   {
//     for(int j=0;j<=w;j++)
//     {
//         cout<<dp[i][j]<<" ";
//     }
//     cout<<"\n";
//   }
   
   cout<<dp[n-1][w];
    return 0;
}


Measured memory_bytes: 79104