#include <iostream>
#include <fstream>
#include <iomanip>

#define N 5001
#define G 10001
#define DEBUG 0
int w[N], p[N], g, n;
int sum[G];
int prev[G];

int main ()
{
    int t;
    std::ifstream fin("rucsac.in");
    std::ofstream fout("rucsac.out");
    fin>>n>>g;
    for(int i=0;i<n;i++)
    {
        fin>>w[i]>>p[i];
    }

    for(int i=0;i<n;i++)
    {
        for(int j=g-w[i];j>=1;j--)
        {
            if(sum[j])
            {   
                if((t=sum[j]+p[i]) > sum[j+w[i]])
                {   
                    sum[j+w[i]] = t;
                    prev[j+w[i]] = j;  
                }
            }             
        }
        
        if(w[i] <= g && sum[w[i]] < p[i])
        {
            sum[w[i]] = p[i]; 
        } 

        if(DEBUG)
        {
            std::cout<<" "<<w[i]<<" "<<p[i]<<std::endl;
            for(int j=1;j<=g;j++)
            {
                std::cout<<std::setw(2)<<j<<" ";
            }
            std::cout<<std::endl;
            for(int j=1;j<=g;j++)
            {
                std::cout<<std::setw(2)<<sum[j]<<" ";
            }
            std::cout<<std::endl;
            for(int j=1;j<=g;j++)
            {
                std::cout<<std::setw(2)<<prev[j]<<" ";
            }
            std::cout<<"\n\n";
        }
    } 
    int max=0;
    for(int i=1;i<=g;i++)
    {
        if(max < sum[i]) 
        {   
            max = sum[i]; 
        }
    }

    fout<<max<<std::endl;

    fout.close();
    fin.close();
    return 0;
}