#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>

#include<functional>

using namespace std;

//--------------mint
long long mul(long long a,long long b,const long long MOD){
    return b ? (mul(a*2,b/2,MOD)+(b&1?a:0))%MOD : 0;
}
 
long long bpow(long long a,long long b,const long long MOD){
    return (b ? bpow(a*a%MOD,b/2,MOD)*(b&1?a:1) : 1) % MOD;
}
 
long long inv(long long a,const long long MOD){
    return bpow(a, MOD-2, MOD);
}
/*
class mInt{
public:
    static const long long mod = 1000000007;
    long long v;
    mInt():v(0){}
    mInt(long long v):v((v%mod+mod)%mod){}
};
mInt& operator += (mInt &a,mInt b){ return a = a.v + b.v; }
mInt& operator -= (mInt &a,mInt b){ return a = a.v - b.v; }
mInt& operator *= (mInt &a,mInt b){ return a = a.v * b.v; }
mInt& operator /= (mInt &a,mInt b){ return a = a.v * inv(b.v,mInt::mod); }
mInt operator + (mInt a,mInt b){ return a += b; }
mInt operator - (mInt a,mInt b){ return a -= b; }
mInt operator * (mInt a,mInt b){ return a *= b; }
mInt operator / (mInt a,mInt b){ return a /= b; }
ostream& operator<<(ostream& os, const mInt& x){ return os << x.v; }
 */

vector<long long> MODS = {1000000007};
template<int kind = 0>
class mint{
public:
    long long v;

    mint() : v(0) {}
    mint(long long v) : v((v % MODS[kind] + MODS[kind]) % MODS[kind]) {}
    long long get_mod() {return MODS[kind];}
};

template<int kind>
ostream& operator<<(ostream& os, const mint<kind>& x){ return os << x.v; }

template<int kind>
mint<kind>& operator += (mint<kind> &a, mint<kind> b){ return a = a.v + b.v; }
template<int kind>
mint<kind>& operator -= (mint<kind> &a, mint<kind> b){ return a = a.v - b.v; }
template<int kind>
mint<kind>& operator *= (mint<kind> &a, mint<kind> b){ return a = a.v * b.v; }
template<int kind>
mint<kind>& operator/= (mint<kind> &a, mint<kind> b) {return a = a.v * inv(b.v, a.get_mod());}
template<int kind>
mint<kind> operator + (mint<kind> a, mint<kind> b){ return a += b; }
template<int kind>
mint<kind> operator - (mint<kind> a, mint<kind> b){ return a -= b; }
template<int kind>
mint<kind> operator * (mint<kind> a, mint<kind> b){ return a *= b; }
template<int kind>
mint<kind> operator / (mint<kind> a, mint<kind> b){ return a /= b; }
template<int kind>
mint<kind>& operator += (mint<kind> &a, long long b){ return a = a.v + b; }
template<int kind>
mint<kind>& operator -= (mint<kind> &a, long long b){ return a = a.v - b; }
template<int kind>
mint<kind>& operator *= (mint<kind> &a, long long b){ return a = a.v * b; }
template<int kind>
mint<kind>& operator /= (mint<kind> &a, long long b){return a = a.v * inv(b, a.get_mod()); }
template<int kind>
mint<kind> operator + (mint<kind> a, long long b){ return a += b; }
template<int kind>
mint<kind> operator - (mint<kind> a, long long b){ return a -= b; }
template<int kind>
mint<kind> operator * (mint<kind> a, long long b){ return a *= b; }
template<int kind>
mint<kind> operator / (mint<kind> a, long long b){ return a /= b; }



namespace detail
{
    template< typename T, std::size_t NDIMS > struct vector_builder
    {
        using type = std::vector< typename vector_builder<T,NDIMS-1>::type > ;

        static type make( std::vector<std::size_t> dims, const T& v = {} )
        {
            const auto vec = std::vector<T>( dims.empty() ? 0 : dims.back(), v ) ;
            if( !dims.empty() ) dims.pop_back() ;
            return vector_builder< std::vector<T>, NDIMS-1 >::make( dims, vec ) ;
        }
    };

    template< typename T > struct vector_builder<T,1>
    {
        using type = std::vector<T> ;

        static type make( std::vector<std::size_t> dims, const T& v = {} )
        { return type( dims.empty() ? 0 : dims.back(), v ) ; }
    };
}



template< typename T, typename... SIZE_T >
auto exvector( const T& v, SIZE_T... dims )
{
    static_assert( sizeof...(dims) != 0, "invalid dimension" ) ;
    std::vector<std::size_t> vec_dims{ dims... } ;
    return detail::vector_builder< T, sizeof...(dims) >::make( vec_dims, v ) ;
}


using namespace std;
//********************  dumps ************************//

template<typename T>
void dump(const T& data, vector<int>& iter) {
    cout << data << " ";
}
template<typename T>
void dump(const vector<T>& data, vector<int>& iter) {
    for(auto elem: data)
        dump(elem, iter);
    cout << endl;
}

template<typename T>
void dump(const vector<vector<T>>& data, vector<int>& iter) {
    for(auto elem : iter) {
        cout << "[" << elem << "]" ;
    }
    cout << endl;
    for(int i=0; i<data.size(); i++) {
        iter.push_back(i);
        dump(data[i], iter);
        iter.pop_back();
    }
    cout << endl;
}

template<typename T>
void dump(const vector<T>& data, int dummy) {
    for(int i=0; i<data.size(); i++) {
        cout <<"[" << i << "] " <<  data[i] << endl;
    }
}
template<typename T>
void dump(const T& data) { // T : data, U = base type val.
    vector<int> iter;
    dump(data, iter);
}

// ===================================
// getter / setter

template<typename T, typename U>
void setval(T& container, vector<int>& pos, U val, int iter) {
    container = (T)val;
}

template<typename T, typename U>
void setval(vector<T>& container, vector<int>& pos, U val, int iter) {
    setval(container[pos[iter]], pos, val, iter+1);
}
/*
template<typename T, typename U>
void setval(T& container, vector<int>& pos,  U val) {
    int iter = 0;
    setval(container, pos, val, iter);    
}
*/
template<typename T, typename U>
void setval(T& container, vector<int> pos,  U val) {
    int iter = 0;
    setval(container, pos, val, iter);    
}

template<typename T>
T getval(T& container, vector<int>& pos, T tmp,int iter) {
    return tmp = container;
}

template<typename T, typename U>
U getval(vector<T>& container, vector<int>& pos, U tmp, int iter) {
    return getval(container[pos[iter]], pos, tmp, iter+1);
}

template<typename T, typename U>
U getval(T& container, vector<int>& pos, U& tmp) {
    int iter = 0;
    return getval(container, pos, tmp, iter);    
}


//-----------------------------------
template<typename T>
void getindices(T& container, vector<int>& iter, vector<vector<int>>& res) {
    res.push_back(iter);
}
template<typename T>
void getindices(vector<T>& container, vector<int>& iter, vector<vector<int>>& res) {
    for(int i=0; i<container.size(); i++) {
        iter.push_back(i);
        getindices(container[i], iter, res);
        iter.pop_back();
    }
}

template<typename T>
vector<vector<int>> getindices(vector<T>& container) {
    vector<int> iter;
    vector<vector<int>> res;
    getindices(container, iter, res);
    return res;

}



template<typename T>
function<T(T, T)>  op_max = [] (T a, T b)-> T{
    return max(a, b);
};
template<typename T>
function<T(T, T)>  op_min = [] (T a, T b)-> T{
    return min(a, b);
};

template<typename T>
function<T(T, T)>  op_sum = [] (T a, T b)-> T{
    return a + b;
};




// prev->cur のように、完全に表を更新するタイプのDPの一般形
template<
    typename Tval,
    typename Tbase

>
vector<Tbase> update_dp_ext(
        Tbase base_vector, 
        int iter,
        Tval initial_value,
        function<Tval(Tval, Tval)> op_merge,
        function<vector<vector<int>>(int, const vector<int>&)> update_pos,
        function<Tval(Tval, int, const vector<int>& , const vector<int>&)> op_edge
         ) {
    Tval tmpval = initial_value;
    auto order = getindices(base_vector);
    vector<Tbase> result;
    result.push_back(base_vector);
    for(int i=0; i<iter; i++) {
        Tbase& prev_table = result.back();
        Tbase current = base_vector;
        for(auto &next : order) {
            vector<vector<int>> prev = update_pos(i, next);
            Tval score = initial_value;
            for(auto &prev_ind : prev) {
                score = op_merge(
                        score, 
                        op_edge(
                            getval(prev_table, prev_ind , tmpval)
                            ,i,  prev_ind, next));
            }
            setval(current, next, score);
        }
        result.push_back(current);
        //dump(result);
    }
    //dump(result);
    return result;
    
} 

template<typename T>
vector<T> ruiseki(vector<T> base, T id, bool reverse = false, 
        function<T(T,T)> op = op_sum<T>) {
    vector<T> res(base.size() + 1, id);
    if(!reverse)
        for(int i=0; i<base.size(); i++) 
            res[i+1] = op(base[i], res[i]);
    if(reverse)
        for(int i=base.size()-1; i>=0; i--) {
            res[i] = op(base[i], res[i+1]);
        }
    return ruiseki;

}





typedef long long LL;

//-------------------------main
int main() {
    int N, W;
    cin >> N >> W;
    LL id = 0;
    auto base = exvector(id, W+1);
    auto input = exvector(id, N, 2);
    for(int i=0; i<N; i++)
        for(int j=0; j<2; j++)
            cin >> input[i][j]; 
    
    function<vector<vector<int>>(int iter, const vector<int>&)> update_pos = 
            [&](int iter, const vector<int> &ind) -> vector<vector<int>>{
        vector<vector<int>> ret;
        ret.push_back(ind);
        int k = ind[0] - input[iter][0];
        if(k >= 0)
            ret.push_back({k});
        return ret;
    };
    int tmp_for_template;
    function<LL(LL, int, const vector<int>&, const vector<int>&)> op_edge = 
            [&](LL val, int iter, const vector<int>& from, const vector<int>& to) -> LL{
        if(to[0] != from[0])
            return val + input[iter][1];
        return val ;

    };

    auto result = update_dp_ext(base, N, id, op_max<LL>, update_pos, op_edge);

    LL ans = accumulate(result.back().begin(), result.back().end(), id, op_max<LL>);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 87088