#include <bits/stdc++.h>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

struct obiect{
  int greutate;
  int profit;

};

obiect v[5000];
int gr[5000];
int pret[5000];
int dp[5000][5000];


int main() {
   int n,g;
   fin>>n>>g;
   
   
   for(int i=1;i<=n;i++){
    fin>>v[i].greutate>>v[i].profit;
    
   }
   
   
   for(int i=1;i<=n;i++){
    for(int j=1;j<=g;j++){
        dp[i][j]=dp[i-1][j];
        if(v[i].greutate<=j && dp[i-1][j-v[i].greutate]+v[i].profit>dp[i][j]){
            dp[i][j]=dp[i-1][j-v[i].greutate]+v[i].profit;
            
            
        }
        
        
    }
   }
   
   fout<<dp[n][g];
   
   
   
   
}