#include <bits/stdc++.h>
#define cin ci
#define cout co
#define int long long
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2")
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
const int inf = 1e9;
int n, g;
struct ob
{
    int weight, price;
};
vector<ob> v;
vector<int> dp;
int32_t main()
{
    cin >> n >> g;
    dp.assign(g + 5, -inf);
    v.resize(n + 5);
    for(int i = 1; i <= n; i ++)
    {
        cin >> v[i].weight >> v[i].price;
    }
    dp[0] = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = g; j >= v[i].weight; j --)
            if(dp[j - v[i].weight] != -inf)
                dp[j] = max(dp[j], dp[j - v[i].weight] + v[i].price);

    int ans = -inf;
    for(int i = 0; i <= g; i ++)
        ans = max(ans, dp[i]);
    cout << ans;
    return 0;
}