#include <fstream>
#include <algorithm>
 
using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int N, Max, rs;
int G[10005], P[5005];
int Dp[2][10005];
 
 
int main()
{
    cin>>N>>G; 
    for(int i=1; i<=N; ++i)
        cin>>G[i]>>P[i];
 
    for(int i=1; i<=N; ++i,rs=1-rs)
        for(int tot=0; tot<=G; ++tot)
        {
            Dp[1-rs][tot] = Dp[l][tot]; 
            if(G[i] <= tot) Dp[1-rs][tot] = max(Dp[1-rs][tot], D[rs][tot - G[i]] + P[i]); 
        }
    cout<<G[rs][G];
 
    return 0;
}