#include <iostream>
#include <string>
#include <vector>
#include <memory.h>
#include <cstdio>
using namespace std;
int w[3410];//重量
int p[3410];//价值
int maxKnow[12880];
int cases;
int value;

int dp(int value)
{
    int i ,j;
    for(i = 1;i <= cases; i++)
       {
        for(j = value; j -w[i]>=0 ;j--)
        {

         if(j < w[i])
               maxKnow[j] = maxKnow[j-w[i]];
            else
               {
                 maxKnow[j] = max(maxKnow[j],maxKnow[j-w[i]] + p[i]);
               }
        }
       }
   int ans;
   for(int i = 0 ;i <= value;i++)
        ans=max(ans,maxKnow[i]);
    return ans;
}


int main()
{

    int i ;
    int max;
    while(scanf("%d %d",&cases,&value)!=EOF)
    {
        memset(w,0,3410*sizeof(int));
        memset(p,0,3410*sizeof(int));
        //memset(c,0,3410*12880*sizeof(int));
        memset(maxKnow,0,12880*sizeof(int));
        for(i = 0;i<cases;i++)
        {
            scanf("%d %d",&w[i+1],&p[i+1]);
        }
        max = dp(value);
        cout << max << endl;
    }
}