#include <iostream>
#include <cstdio>

#define NMaxim 10005

using namespace std;

int N, G;
int W[NMaxim], P[NMaxim];
int dp[10005];

void Read()
{
    scanf("%d%d", &N, &G);

    for(int i=1; i<=N; ++i)
        scanf("%d%d", &W[i], &P[i]);
}

void Solve()
{
    for(int i=1; i<=N; ++i)
        for(int j=G; j>=W[i]; --j)
    {
        if(dp[j] < P[i]+dp[j-W[i]])
            dp[j]=P[i]+dp[j-W[i]];
    }

    cout<<dp[G];
}

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

   Read();
   Solve();
    return 0;
}