/******************************************************************************

Welcome to GDB Online.
  GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby, 
  C#, OCaml, VB, Perl, Swift, Prolog, Javascript, Pascal, COBOL, HTML, CSS, JS
  Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int g[1001],p[1001],dp[1001][1001],n,G;
int main()
{
    fin>>n>>G;
    for(int i=1;i<=n;i++)
    {
        fin>>g[i]>>p[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=G;j++)
        {
            
        dp[i][j] = dp[i-1][j]; 
        if (j >= g[i]) {
            dp[i][j] = max(dp[i][j], dp[i-1][j - g[i]] + p[i]); 
        }
    

        }
    }
    fout<<dp[n][G];
}