Language: C++

// Vaidik Patel(India)
// DA-IICT
#include <bits/stdc++.h>
using namespace std;
//********************************************
#include<ext/pb_ds/assoc_container.hpp> // include the associative containers or group of templates such as set, multimap, map etc.
#include<ext/pb_ds/tree_policy.hpp> // include the tree_order_statistics_node update
using namespace __gnu_pbds; //necessary for the GNU based Policy based data structures.
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//********************************************

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
int INF = (int)1e9;
ll INFINF = (ll)1e18 + 10;
const ld PI = 3.14159265358979323846;
#define precision(x,d) cout<<fixed<<setprecision(d)<<x
#define minheap priority_queue<ll,vector<ll>,greater<ll> >
#define maxheap priority_queue<ll,vector<ll>,less<ll> >
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rFOR(i,a,b) for(ll i=a;i>=b;i--)
#define deb1(x) cout<<#x<<" : "<<x<<endl;
#define deb2(x,y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<endl;
#define deb3(x,y,z) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\t"<<#z<<" : "<<z<<endl;
#define deb4(x,y,z,w) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\t"<<#z<<" : "<<z<<"\t"<<#w<<" : "<<w<<endl;
#define deb5(a, b, c, d, e)    cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl;
#define deb6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl;
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define checkbit(n,b) ( (n >> b) & 1)
#define mkp make_pair
#define ff first
#define ss second
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define TIME cerr << "Time Elapsed : "<<1.0*clock()/CLOCKS_PER_SEC<<"\n";
#define lc 2*idx
#define rc 2*idx+1
ll powermodm(ll x,ll n,ll mod)
{ll result=1;while(n>0){if(n % 2 ==1)result=(result * x)%mod;x=(x*x)%mod;n=n/2;}return result;}
ll GCD(ll , ll );
ll LCM(ll ,ll);
ll power(ll ,ll);
ll choose(ll,ll);
int ones(ll);
void extendedEuclid(ll, ll);
ll MMI(ll, ll);
void fastscan(int &);
bool checkithbit(ll,ll); // ith bit is zero or not
vector<ll>SegmentTree;
void Build_Segment_Tree(vector<ll>&a,ll idx,ll l,ll r);
ll sum(ll idx,ll sl,ll sr,ll l,ll r);
void update(ll idx,ll sl,ll sr,ll value,ll id);
vector<ll>prime;
void findprime(void);
ll phi(ll num);
vector<int>isprime;
void precomputeprime(int N);
vector<int>prephi;
void precomputephi(int N);
int read();
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
#define pb push_back
#define M  1000000007
//////////////////////////////////////////////////////////////////////////////


int main()
{

    

    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    ll n,w;
    cin>>n>>w;
    vvll a(n,vll(2));
    //vvll dp(n+1,vll(w+1,0));
    unordered_map<pair<ll,ll>,ll>mp;
    FOR(i,0,n)
    {
        cin>>a[i][0]>>a[i][1];
    }
    FOR(i,1,n+1)
    {
        FOR(j,0,w+1)
        {
            if(a[i-1][0]>j)
            {
                mp[{i,j}]=mp[{i-1,j}];
                //dp[i][j]=dp[i-1][j];
            }
            else
            {
                mp[{i,j}]=max(mp[{i-1,j}],a[i-1][1]+mp[{i-1,j-a[i-1][0]}]);
               // dp[i][j]=max(dp[i-1][j],a[i-1][1]+dp[i-1][j-a[i-1][0]]);
            }
        }
    }
    cout<<mp[{n,w}]<<"\n";
    return 0;
}
//////////////////////////////////////////////////////////////////////////
//precomputephi()
void precomputephi(int N)
{
    prephi.resize(N);

    FOR(i,0,N)
    {
        prephi[i]=i;
    }

    for(int i=1;i<N;i++)
    {
        if(isprime[i])
        {
            for(int j=i;j<N;j+=i)
            {
                prephi[j]=prephi[j]-(prephi[j]/i);
            }
        }
    }
}

//precomputedprime()
void precomputeprime(int N)
{
    isprime.resize(N);
    isprime.assign(N,1);
    isprime[0]=0;
    isprime[1]=0;
    for(int i=2;i*i<=500005;i++)
    {
        if(isprime[i])
        {
            for(int j=i*i;j<=500005;j+=i)
            {
                isprime[j]=0;
            }
        }
    }
}
//"""euler totient function""": counts the number of integers between 1 and n inclusive, which are coprime to n.
ll phi(ll num) // find using factorization in O(sqrt(N)).....
{
    ll result=num;
    for(ll i=2;i*i<=num;i++)
    {
        if(num%i==0)
        {
            while(num%i==0)
            {
                num/=i;
            }
            result-=(result/i);
        }
    }
    if(num>1)
    {
        result-=(result/num);
    }
    return result;
}

void findprime(void)
{
    int N=1e6+5;
    vector<bool>isprime(N,1); //up to 1e6+5 number
    for(int i=2;i*i<=N;i++)
    {
        if(isprime[i])
        {
            for(int j=i*i;j<=N;j+=i)
            {
                if(isprime[j])
                {
                    isprime[j]=0;
                }
            }
        }
    }

    for(int i=2;i<=N;i++)
    {
        if(isprime[i])
        {
            prime.pb(i);
        }
    }

}

bool checkithbit(ll a,ll i)
{
if(a & (1 << i))
{
return  true;
}
else
{
return false;
}
}
ll GCD(ll a , ll b)
{
    if(b==0)
        return a;
    else
        return GCD(b,a%b);
}
ll LCM(ll a,ll b){return (max(a,b)/GCD(a,b))*min(a,b);}

ll power(ll a , ll n)
{
    unsigned long long int result=1,x=a;
    while(n>0)
    {
        if(n % 2 ==1)
            result=result * x;
        x = x * x;
        n=n/2;
    }
    return result;
}
ll choose(ll n,ll k)
{
    if(k==0)  return 1;
    return (n* choose(n-1,k-1))/k;
}
int ones(ll n)
{
    int c=0;
    while(n)
    {
        n=n&(n-1);
        c++;
    }
    return c;
}
//store gcd of a,b in d
//store solution of a*x + b*y = d in x,y
// if gcd(a,b)=1 then x = a^(-1)(mod b) and y = b^(-1)(mod a)
ll d, x, y;
void extendedEuclid(ll A, ll B) {
    if(B == 0) {
        d = A;
        x = 1;
        y = 0;
    }
    else
    {
        extendedEuclid(B, A%B);
        int temp = x;
        x = y;
        y = temp - (A/B)*y;
    }
}
// return modulo inverse of a wrt modulo p(should be prime)
// retunt -1 if modulo inverse does not exist
ll MMI(ll a, ll p)
{
    extendedEuclid(a,p);
    if(d==1 && p!=1)
        return ((x%p)+p)%p;
    else
        return -1;
}

//Fastest way to read Input
void fastscan(int &number)
{
    bool negative = false;
    register int c;
    number = 0;
    c = getchar();
    if (c=='-')
    {
        negative = true;
        c = getchar();
    }
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;
    if (negative)
        number *= -1;
}
inline int read () {
    int ret = 0, t = 1;
    char c = getchar();
    while ((c < '0' || c > '9') && c != '-') c = getchar();
    if (c == '-') t = -1, c = getchar();
    while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();
    return ret * t;
}
void Build_Segment_Tree(vector<ll>&a,ll idx,ll l,ll r) //where l and r is query range.
{
  if(l==r)
  {
    SegmentTree[idx]=a[l];
  }
  else
  {
    ll mid=(l+r)/2ll;
    Build_Segment_Tree(a,(2ll*idx),l,mid);
    Build_Segment_Tree(a,(2ll*idx)+1,mid+1,r);
    SegmentTree[idx]=SegmentTree[2ll*idx]+SegmentTree[2ll*idx+1];
  }
}
ll sum(ll idx,ll sl,ll sr,ll l,ll r) //here [sl...sr] segment range associate at idx index. where l and r is query range.
{
    if(l>r)
    {
        return 0;
    }
    if(sl==l && sr==r)
    {
        return SegmentTree[idx];
    }


    ll mid=(sl+sr)/2;
    return sum(2ll*idx,sl,mid,l,min(r,mid))+sum(2ll*idx+1,mid+1,sr,max(mid+1,l),r);
}

void update(ll idx,ll sl,ll sr,ll value,ll id)
{
    if(sl==sr && sl==id)
    {
        SegmentTree[idx]=value;
    }
    else
    {
        ll mid=(sl+sr)/2ll;
        if(id<=mid)
        {
            update(2ll*idx,sl,mid,value,id);
        }
        else
        {
            update(2ll*idx+1,mid+1,sr,value,id);
        }
        SegmentTree[idx]=SegmentTree[2ll*idx]+SegmentTree[2ll*idx+1];
    }
}
/*
note:
//a.resize(unique(a.begin(), a.end()) - a.begin()); use for create array unique element...
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); shuffle(g1.begin(), g1.end(), rng);(g1 is array name) for choose random number
//int grand(int x) {
    return uniform_int_distribution<int>(0, x - 1)(rng);
}
//use once(num) give no of 1 in its binary form
//use give (int)log2(num)+1 give no of digits in its binary form
//bitset<64>(num).to_string() convert decimal to num64 bit binary number
//stoull(str, nullptr, 2) convert str in binary form to decimal number
// "max" priority queue: priority_queue<ll, vector<ll>, less<ll> >pq;   #select max element as top()#
// "min" priority queue: priority_queue<ll, vector<ll>, greater<    ll> >pq; #select min element as top()#
//set<int> inbuit sort accending order (set<int,less<int>>)
//set<int,greater<int>> sort element in decreasing order
// int  __builtin_popcount(unsigned int)
--->It returns the numbers of set bits in an integer (the number of ones in the binary representation of the integer).
///for finding xnor from xor
        x1=Xor
    x2=Xnor
    ll x1=a ^ b;

        ll num=max(a,b);

        ll xx=log2(num)+ 1;   (length of num in binary form)
    ****ll t=(1 << xx) - 1;  (set all xx length bits to 1)
        ll x2=x1 ^ t;            (get xnor via xor using t)


--->Dilworth's theorem:-
        this theorem says that the minimum number of non-decreasing sequences we need to cover the
        whole sequence equals the length of least decreasing subsequence.
----->a + b = (a xor b) +( 2 * (a & b)); ///very imp
*/



Compiler output:
a.cc: In function 'int main()':
a.cc:86:34: error: use of deleted function 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = std::pair<long long int, long long int>; _Tp = long long int; _Hash = std::hash<std::pair<long long int, long long int> >; _Pred = std::equal_to<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >]'
   86 |     unordered_map<pair<ll,ll>,ll>mp;
      |                                  ^~
In file included from /usr/include/c++/14/unordered_map:41,
                 from /usr/include/c++/14/functional:63,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:53,
                 from a.cc:3:
/usr/include/c++/14/bits/unordered_map.h:148:7: note: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = std::pair<long long int, long long int>; _Tp = long long int; _Hash = std::hash<std::pair<long long int, long long int> >; _Pred = std::equal_to<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >]' is implicitly deleted because the default definition would be ill-formed:
  148 |       unordered_map() = default;
      |       ^~~~~~~~~~~~~
/usr/include/c++/14/bits/unordered_map.h: At global scope:
/usr/include/c++/14/bits/unordered_map.h:148:7: error: use of deleted function 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::pair<long long int, long long int>; _Value = std::pair<const std::pair<long long int, long long int>, long long int>; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<long long int, long long int> >; _Hash = std::hash<std::pair<long long int, long long int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]'
In file included from /usr/include/c++/14/bits/unordered_map.h:33:
/usr/include/c++/14/bits/hashtable.h:539:7: note: 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::pair<long long int, long long int>; _Value = std::pair<const std::pair<long long int, long long int>, long long int>; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<long long int, long long int> >; _Hash = std::hash<std::pair<long long int, long long int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]' is implicitly deleted because the default definition would be ill-formed:
  539 |       _Hashtable() = default;
      |       ^~~~~~~~~~
/usr/include/c++/14/bits/hashtable.h:539:7: error: use of deleted function 'std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _Traits>::_Hashtable_base() [with _Key = std::pair<long long int, long long int>; _Value = std::pair<const std::pair<long long int, long long int>, long long int>; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<long long int, long long int> >; _Hash = std::hash<std::pair<long long int, long long int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, false, true>]'
In file included from /usr/include/c++/14/bits/hashtable.h:35:
/usr/include/c++/14/bits/hashtable_policy.h:1731:7: note: 'std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _Traits>::_Hashtable_base() [with _Key = std::pair<long long int, long long int>; _Value = std::pair<const std::pair<long long int, long long int>, long long int>; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<long long int, long long int> >; _Hash = std::hash<std::pair<long long int, long long int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, false, true>]' is implicitly deleted because the default definition would be ill-formed:
 1731 |       _Hashtable_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1731:7: error: use of deleted function 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_Hash_code_base() [with _Key = std::pair<long long int, long long int>; _Value = std::pair<const std::pair<long long int, long long int>, long long int>; _ExtractKey = std::__detail::_Select1st; _Hash = std::hash<std::pair<long long int, long long int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true]'
/usr/include/c++/14/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hashtable_ebo_helper<_Nm, _Tp, true>::_Hashtable_ebo_helper() [with int _Nm = 1; _Tp = std::hash<std::pair<long long int, long long int> >]':
/usr/include/c++/14/bits/hashtable_policy.h:1328:7:   required from here
 1328 |       _Hash_code_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1245:49: error: use of deleted function 'std::hash<std::pair<long long int, long long int> >::hash()'
 1245 |       _Hashtable_ebo_helper() noexcept(noexcept(_Tp())) : _Tp() { }
      |                                                 ^~~~~
In file included from /usr/include/c++/14/string_view:50,
                 from /usr/include/c++/14/bits/basic_string.h:47,
                 from /usr/include/c++/14/string:54,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52:
/usr/include/c++/14/bits/functional_hash.h:102:12: note: 'std::hash<std::pair<long long int, long long int> >::hash()' is implicitly deleted because the default definition would be ill-formed:
  102 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/14/bits/functional_hash.h:102:12: error: no matching function for call to 'std::__hash_enum<std::pair<long long int, long long int>, false>::__hash_enum()'
/usr/include/c++/14/bits/functional_hash.h:83:7: note: candidate: 'std::__hash_enum<_Tp, <anonymous> >::__hash_enum(std::__hash_enum<_Tp, <anonymous> >&&) [with _Tp = std::pair<long long int, long long int>; bool <anonymous> = false]'
   83 |       __hash_enum(__hash_enum&&);
      |       ^~~~~~~~~~~
/usr/include/c++/14/bits/functional_hash.h:83:7: note:   candidate expects 1 argument, 0 provided
/usr/include/c++/14/bits/functional_hash.h:102:12: error: 'std::__hash_enum<_Tp, <anonymous> >::~__hash_enum() [with _Tp = std::pair<long long int, long long int>; bool <anonymous> = false]' is private within this context
  102 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/14/bits/functional_hash.h:84:7: note: declared private here
   84 |       ~__hash_enum();
      |       ^
/usr/include/c++/14/bits/hashtable_policy.h:1245:49: note: use '-fdiagnostics-all-candidates' to display considered candidates
 1245 |       _Hashtable_ebo_helper() noexcept(noexcept(_Tp())) : _Tp() { }
      |                                                 ^~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1328:7: note: 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_Hash_code_base() [with _Key = std::pair<long long int, long long int>; _Value = std::pair<const std::pair<long long int, long long int>, long long int>; _ExtractKey = std::__detail::_Select1st; _Hash = std::hash<std::pair<long long int, long long int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true]' is implicitly deleted because the default definition would be ill-formed:
 1328 |       _Hash_code_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1328:7: error: use of deleted function 'std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<long long int, long long int> >, true>::~_Hashtable_ebo_helper()'
/usr/include/c++/14/bits/hashtable_policy.h:1242:12: note: 'std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<long long int, long long int> >, true>::~_Hashtable_ebo_helper()' is implicitly deleted because the default definition would be ill-formed:
 1242 |     struct _Hashtable_ebo_helper<_Nm, _Tp, true>
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1242:12: error: use of deleted function 'std::hash<std::pair<long long int, long long int> >::~hash()'
/usr/include/c++/14/bits/functional_hash.h:102:12: note: 'std::hash<std::pair<long long int, long long int> >::~hash()' is implicitly deleted because the default definition would be ill-formed:
  102 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/14/bits/functional_hash.h:102:12: error: 'std::__hash_enum<_Tp, <anonymous> >::~__hash_enum() [with _Tp = std::pair<long long int, long long int>; bool <anonymous> = false]' is private within this context
/usr/include/c++/14/bits/functional_hash.h:84:7: note: declared private here
   84 |       ~__hash_enum();
      |       ^
/usr/include/c++/14/bits/hashtable_policy.h:1731:7: note: use '-fdiagnostics-all-candidates' to display considered candidates
 1731 |       _Hashtable_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1731:7: error: use of deleted function 'std::__detail::_Hash_code_base<std::pair<long long int, long long int>, std::pair<const std::pair<long long int, long long int>, long long int>, std::__detail::_Sele