#include <fstream>
#include <deque>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int dp[5001][10001],w[5001],v[5001];


int main()
{
    int n,g;
    cin>>n>>g;
    for(int i = 1;i<=n;i++)
    cin>>w[i]>>v[i];
    
    dp[1][w[1]] = v[1];
    for(int i =2 ; i<=n;i++){
        for(int j  =1 ;j<=g;j++){
            dp[i][j] = dp[i-1][j];
            if(w[i]<=j and dp[i-1][j-w[i]]!=0 and dp[i][j]<dp[i][j-w[i]] + v[i])
            dp[i][j]= dp[i][j-w[i]] + v[i];
            
        }
    }
    int total=0;
    for(int i = 1;i<=g;i++)
        total = max(total,dp[n][i]);
    cout<<total;
}