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

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

int n,g,p[5005],w[5005],dp[10005];

void rucsac()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=g;j>=w[i];j--)
        {
            dp[j]=max(dp[j],dp[j-w[i]]+p[i]);
        }
    }
    fout<<dp[g];
}
 int main()
 {
     fin>>n>>g;
     for(int i=1;i<=n;i++)
     {
         fin>>w[i]>>p[i];
     }
     rucsac();
     return 0;
 }