#include <bits/stdc++.h>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int dp[10005];
vector< pair <int,int>> v;

int main()
{
    int n,g;
    f>>n>>g;
    for(int i=1; i<=n; i++)
    {
        int x,y;
        f>>x>>y;
        v.push_back({x,y});
    }
    for(int j=0; j<=g; j++)
        dp[j]=0;
    for(int i=0; i<n; i++)
        for(int j=g; j>=v[i].first; --j)
            dp[j]=max(dp[j],dp[j-v[i].first]+v[i].second);
    g<<dp[g];
    return 0;
}