#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXN 5010
#define MAXG 10010

int N, G, Pmax;
int W[MAXN], P[MAXN];
int D[MAXN][MAXG];

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

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

    // Dinamica D[i][cw] - profitul maxim pe care-l putem obtine adaugand o submultime a primelor i obiecte, insumand greutatea cw
    for(int i = 1; i <= N; ++i)
        for(int cw = 0; cw <= G; ++cw)
        {
            // Mai intai nu punem obiectul i.
            D[i][cw] = D[i-1][cw];

            // Daca acest lucru duce la o solutie curenta mai buna, adaugam obiectul i la o solutie anterioara.
            if(W[i] <= cw)
                D[i][cw] = max(D[i][cw], D[i - 1][cw - W[i]] + P[i]);
        }

    // Solutia se va afla in statea D[N][G]
    Pmax = D[N][G];

    // Afisare
    printf("%d\n", Pmax);

    return 0;
}
/*
#include <iostream>
#include<cstdio>
#define max(a,b) ((a)>(b) ? (a):(b))
FILE * f=fopen("rucsac.in","r");
FILE * g=fopen("rucsac.out","w");
int n,p;
struct pula {int x,y;}c[100];
int a[5001][10001];
void citire( )
{ int i,x1,y1;
    fscanf(f,"%d %d",&n,&p);
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%d %d",&x1,&y1);
    c[i].x=x1;
    c[i].y=y1;
    }
}
using namespace std;
void rezolvare( )
{ int i,j,ok;
    for(i=1;i<=p;i++)
    {
        if(i==c[1].x)
            a[1][i]=c[1].y;
    }
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=p;j++)
    { a[i][j]=a[i-1][j];
        if(j-c[i].x>=0)
        a[i][j]=max(a[i][j],a[i-1][j-c[i].x]+c[i].y);
    }
    }
}




int main()
{ int i,j;
//cout<<max(1,2);
citire( );
rezolvare( );
for(i=1;i<=n;i++)
{
    for(j=1;j<=p;j++)
    {
        cout<<a[i][j]<<" ";
    }
    cout<<endl;
}
fprintf(g,"%d",a[n][p]);
return 0;
}
*/