#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int n,gm,g[5001],v[5001],dp[10001],a;
int main()
{
    fin >>n>>gm;
    for (int i=1;i<=n;i++)
        {fin >>g[i]>>v[i];}
    for (int i=1;i<=n;i++)
        {for (int j=gm-g[i];j>=0;j--)
             {if (dp[j]!=-1) {dp[j+g[i]]=max(dp[j]+v[i],dp[j+g[i]]);}}}
    for (int i=0;i<=gm;i++)
        {a=max(a,dp[i]);}
    fout <<a;
    return 0;
}