#include<iostream>
using namespace std;
int f[12881];  //f[k]表示：當背包的容量為k時的最大價值
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int Num,TotalWeight,i,k,j,weight[12881],value[12881];
        cin>>Num>>TotalWeight;
    f[0]=0;
    for(i=0;i<Num;i++)
        cin>>weight[i]>>value[i];
    for(i=0;i<Num;i++)
        for(k=TotalWeight;k>=weight[i];k--)
        {
            f[k]=max(f[k],(f[k-weight[i]]+value[i]));
            //在max中的兩個參數f[k], 和f[k-weight[i]]+value[i]都是表示在背包容量為k時的最大價值
            //f[k]是這個意思，就不用說了。
            //而f[k-weight[i]]+value[i]也表示背包容量為k時的最大價值是為什么呢？
            //首先，f[k-weight[i]]表示的是背包容量為k-weight[i]的容量，也就是說f[k-weight[i]]
            //表示的是容量還差weiht[i]才到k的價值，+walue[i]恰好彌補了差的這個價值。所以……

            //如果你對f[k]=max(f[k],(f[k-weight[i]]+value[i]));這句話不是很清楚，
            //下面的這句代碼會對你有幫助
            //cout<<"i="<<i+1<<"  f["<<k<<"]="<<f[k]<<endl;
        }
    cout<<f[TotalWeight]<<endl;
    return 0;
}