#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
const int max_n=5001;
const int max_g=10001;
int dp[max_n][max_g];

struct t_object {
    int weight;
    int profit;
};
int main()
{
    int n,greutate;
    fin>>n>>greutate;
    t_object objs[max_n];
    for(int i=1;i<=n;i++)
    {
        int curr_greutate;
        int curr_profit;
        fin>>curr_greutate>>curr_profit;
        t_object obj={curr_greutate,curr_profit};
        objs[i]=obj;
    }
    for(int idx=1;idx<=n;idx++)
    for(int g=1;g<=greutate;g++)
    {t_object obj=objs[idx];

     if(obj.weight>g)
     dp[idx][g]=dp[idx-1][g];
     else
     {//are loc in ghiozdan
      //consideram 2 cazuri
      //cazul 1- il punem in ghiozdan
      int profit1=dp[idx-1][g];
      int profit2=obj.profit+dp[idx-1][g-obj.weight];
      dp[idx][g]=max(profit1,profit2);
     }
    }
    fout<<dp[n][greutate];
    return 0;
}