// Take care of mod becoming -ve


#include<bits/stdc++.h>
#define fro(i,s,e) for(auto i=s;i<=e;++i)
#define int long long
#define ld long double
#define fr(i,n) for(auto i=0;i<n;i++)
#define ff first
#define ss second
#define mp make_pair
#define vi std::vector<int>
#define mii map<int,int>
#define setbits(x) __builtin_popcountll(x)
#define zrbits(x) __builtin_ctzll(x)
#define vii std::vector<int,int>
#define tc int t;cin>>t;while(t--)
#define FILE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout)
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define inp(a) long long a;cin>>a;
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];
#define endl "\n"
const int mod = 1000000007;
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
using namespace std;
const int MAXN = 100005;
const int INF = 1e9+5;
#define fill(s,x) memset(s,x,sizeof(s));
inline int add(int a, int b) {return ((a % mod + b % mod) % mod);}
inline int sub(int a, int b) {return ((a % mod - b % mod) % mod);}
inline int mult(int a, int b, int md) {return ((a % md) * (b % md)) % md;}
// typedef tree<int, null_type, less<int>, rb_tree_tag,
//         tree_order_statistics_node_update> indexed_set;
// Use __gcd(a,b) for gcd
// find(all(x),key) to get the iterator and its index is obtained by find(all(x),key)-x.begin()
// find_if(iterator_first,iterator_last,unary function) returns first iterator if any element corresponding to unary function exists and if no such element is found it retrurns the last iterator
/*For example:
find_if(all(x),isodd) for x being a vector{10,25,40,55}; *it returns 25*/
/*search(all(v1),all(v2),pred) searches for all the elements of v2 present in v1 based on pred function the iterator correspond
to the first element of sequence if it exists and if not then th elast iterator is obtained.*/
int binsearch(int* a, int key) {
    int index = 0;
    int n = sizeof(a) / sizeof(a[0]);
    for (auto jump = n / 2; jump >= 1; jump++) {
        while (index + jump < n and a[index + jump] <= key)index += jump;
    }
    if (a[index] == key)
        return index;
    return -1;
}
long long power(long long a, long long b, int md) {
    long long ans = 1;
    while (b > 0) {
        if (b & 1) {ans = (ans * a) % md;}
        a = (a * a) % md;
        b >>= 1;
    }
    return ans;
}
int findDuplicate(vector<int>& nums) {
    int ans;
    fr(i, nums.size()) {
        if (nums[abs(nums[i]) - 1] > 0)
            nums[abs(nums[i]) - 1] = -nums[abs(nums[i]) - 1];
        else
            ans = nums[i];
    }
    return abs(ans);
}
bool  in_range(int i, int start, int end) {
    return (i >= start && i <= end);
}
// int power[MAXN];
bool all_character_same(string s) {
    return (s.find_first_not_of(s[0]) == string::npos);
}
int signum(int x) {
    if (x != 0)
        return x > 0 ? 1 : -1;
    return 0;
}
void max_self(int &a,int b){
    a=max(a,b);
}
// Maximum sub-array sum
void solve() {
    int n,W;
    cin>>n>>W;
    vi dp(W+1);//0....W
    //dp[i] indicates the total value with weight exactly equal to i
    fr(item,n){
        int weight,value;
        cin>>weight>>value;
        for(int weight_already=W-weight;weight_already>=0;weight_already--){
            max_self(dp[weight_already+weight], dp[weight_already]+value);
        }
    }
    cout<<*max_element(all(dp))<<'\n';
    
}


int32_t main() {
    fio;
// #ifndef ONLINE_JUDGE
//     FILE;
// #endif
    // indexed_set s;
    // s.insert(2);
    // s.insert(3);
    // s.insert(7);
    // s.insert(9);
    // auto x = s.find_by_order(2);
    // cout << *x << endl;

    // tc {
    //     solve();
    // }
    solve();

    printclock;
    return 0;
}


Measured memory_bytes: 1024