#include <bits/stdc++.h>
#define ll long long
//#define int ll
using namespace std;

ifstream f ("rucsac.in");
ofstream g ("rucsac.out");

int n,G,dp[10005];

main()
{
    f>>n>>G;
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        int w,p;
        f>>w>>p;
        for(int j=G-w;j>=0;--j)
        {
            dp[j+w]=max(dp[j]+p,dp[j+w]);
            ans=max(ans,dp[j+w]);
        }
    }
    g<<ans;

}