# CFR 808 E. Selling Souvenirs ( Ad hoc, Monotonous )

Problem - 808E - Codeforces

1 ≤ N ≤ 1e5
1 ≤ M ≤ 3e5
1 ≤ W[ i ] ≤ 3
1 ≤ C[ i ] ≤ 1e9

O( N lg N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 1e5 );
const int MAXM = int( 3e5 );

int N, M;
int W[ MAXN ], C[ MAXN ];

vector< int > vec[ 3 + 1 ];

signed main() {
ios::sync_with_stdio( 0 );
cin >> N >> M;
for( int i = 0; i < N; ++i ) {
cin >> W[ i ] >> C[ i ];
vec[ W[ i ] ].emplace_back( C[ i ] );
}
for( int i = 1; i <= 3; ++i ) {
sort( vec[ i ].begin(), vec[ i ].end(), greater< int >() );
}
long long ans = 0;
if( not vec[ 1 ].empty() ) { // suppose optimal strategy takes odd number of elements from vec[ 1 ]
long long sum = vec[ 1 ][ 0 ];
vector< int > f = vec[ 2 ];
for( int i = 1; i + 2 <= vec[ 1 ].size(); i += 2 ) {
f.emplace_back( vec[ 1 ][ i ] + vec[ 1 ][ i + 1 ] );
}
sort( f.begin(), f.end(), greater< int >() );
int ptr = 0;
long long wei = M - 1;
while( ptr < f.size() and wei >= 2 ) {
wei -= 2;
sum += f[ ptr++ ];
}
ans = max( ans, sum );
for( int i = 0; i < vec[ 3 ].size(); ++i ) {
wei -= 3;
sum += vec[ 3 ][ i ];
while( 0 < ptr and wei < 0 ) {
wei += 2;
sum -= f[ --ptr ];
}
if( wei < 0 ) break;
ans = max( ans, sum );
}
}
{ // suppose optimal strategy takes even number of elements from vec[ 1 ]
long long sum = 0;
vector< int > f = vec[ 2 ];
for( int i = 0; i + 2 <= vec[ 1 ].size(); i += 2 ) {
f.emplace_back( vec[ 1 ][ i ] + vec[ 1 ][ i + 1 ] );
}
sort( f.begin(), f.end(), greater< int >() );
int ptr = 0;
long long wei = M;
while( ptr < f.size() and wei >= 2 ) {
wei -= 2;
sum += f[ ptr++ ];
}
ans = max( ans, sum );
for( int i = 0; i < vec[ 3 ].size(); ++i ) {
wei -= 3;
sum += vec[ 3 ][ i ];
while( 0 < ptr and wei < 0 ) {
wei += 2;
sum -= f[ --ptr ];
}
if( wei < 0 ) break;
ans = max( ans, sum );
}
}
cout << ans << endl;
return 0;
}
```