#include <iostream>
#include <stdio.h>

using namespace std;

#define min(a,b) (((a) <(b)) ? (a) : (b))
#define max(a,b) (((a) > (b)) ? (a) : (b))

short unsigned int weight[5001];
short unsigned int value[5001];
int m[2][10001];
int main()
{
    int n,g,i;
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d %d",&n,&g);
    for(i=1;i<=n;++i)
        scanf("%d%d",&weight[i],&value[i]);
    int j;
    bool linie = 0;
    for(i=1;i<=n;++i,linie= !linie)
    {
        for(j=1;j<=g;++j)
        {
            m[linie][j] = m[!linie][j];
            if(weight[i] <= j)
            {
                m[linie][j] = max(m[!linie][j],m[!linie][j-weight[i]] + value[i]);
            }
        }
    }
    printf("%d\n",m[!linie][g]);
    return 0;
}