#include <iostream>
#include <stdio.h>
using namespace std;

int a[3][10005], n, gmax, pmax=0;

struct obiect
{
    int v;
    int g;
}v[5005];

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

    cin>>n>>gmax;
    for(int i=1; i<=n; i++)
        scanf("%d %d \n", &v[i].g, &v[i].v);

    int x=1, y=2;

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=gmax; j++)
        {
            a[x][j]=a[y][j];

            if(j-v[i].g>=0)
                a[x][j]=max(a[x][j],a[y][j-v[i].g]+v[i].v);

        }
        swap(x,y);
    }

    if(n%2==0)
        cout<<a[2][gmax];
    else
        cout<<a[1][gmax];

    return 0;
}