# CFR 808 F. Card Game ( Flow, Binary Search )

Problem - 808F - Codeforces

1 ≤ N ≤ 100
1 ≤ K ≤ 1e5
1 ≤ P[ i ] ≤ 1000
1 ≤ C[ i ] ≤ 1e5
1 ≤ L[ i ] ≤ N

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

template< class T >
struct Dinic {
static const int MAXV = 10000;
static const T INF = 0x3f3f3f3f;
struct Edge {
int v;
T f;
int re;
Edge( int _v, T _f, int _re ): v( _v ), f( _f ), re( _re ) {}
};
int n, s, t, level[ MAXV ];
vector< Edge > E[ MAXV ];
int now[ MAXV ];
Dinic( int _n, int _s, int _t ): n( _n ), s( _s ), t( _t ) {}
void add_edge( int u, int v, T f ) {
E[ u ].emplace_back( v, f, E[ v ].size() );
E[ v ].emplace_back( u, 0, E[ u ].size() - 1 );
}
bool BFS() {
memset( level, -1, sizeof( level ) );
queue< int > que;
que.emplace( s );
level[ s ] = 0;
while( not que.empty() ) {
int u = que.front();
que.pop();
for( auto it: E[ u ] ) {
if( it.f > 0 and level[ it.v ] == -1 ) {
level[ it.v ] = level[ u ] + 1;
que.emplace( it.v );
}
}
}
return level[ t ] != -1;
}
T DFS( int u, T nf ) {
if( u == t ) return nf;
T res = 0;
while( now[ u ] < E[ u ].size() ) {
Edge &it = E[ u ][ now[ u ] ];
if( it.f > 0 and level[ it.v ] == level[ u ] + 1 ) {
T tf = DFS( it.v, min( nf, it.f ) );
res += tf; nf -= tf; it.f -= tf;
E[ it.v ][ it.re ].f += tf;
if( nf == 0 ) return res;
} else ++now[ u ];
}
if( not res ) level[ u ] = -1;
return res;
}
T flow( T res = 0 ) {
while( BFS() ) {
T temp;
memset( now, 0, sizeof( now ) );
while( temp = DFS( s, INF ) ) {
res += temp;
}
}
return res;
}
};

const int SOURCE = 100;
const int SINK = 101;

const int MAXN = 100;
const int MAXP = 1000;
const int MAXC = int( 1e5 );

int np[ MAXC * 2 + 1 ]; // not prime

int N, K;
int P[ MAXN ], C[ MAXN ], L[ MAXN ];

int score( int lv ) {
vector< int > ps( MAXC + 1 );
vector< int > dsctz;
for( int i = 0; i < N; ++i ) {
if( lv < L[ i ] ) continue;
dsctz.emplace_back( C[ i ] );
if( C[ i ] == 1 ) {
ps[ 1 ] = max( ps[ 1 ], P[ i ] );
} else {
ps[ C[ i ] ] += P[ i ];
}
}
sort( dsctz.begin(), dsctz.end() );
dsctz.erase( unique( dsctz.begin(), dsctz.end() ), dsctz.end() );
auto id = [ & ]( int x ) { return lower_bound( dsctz.begin(), dsctz.end(), x ) - dsctz.begin(); };
Dinic< int > no_one( 102, SOURCE, SINK ), has_one( 102, SOURCE, SINK );
for( int i = 2; i <= MAXC; ++i ) if( ps[ i ] ) {
if( i & 1 ) {
no_one.add_edge( id( i ), SINK, ps[ i ] );
has_one.add_edge( id( i ), SINK, ps[ i ] );
} else {
no_one.add_edge( SOURCE, id( i ), ps[ i ] );
if( np[ i + 1 ] ) {
has_one.add_edge( SOURCE, id( i ), ps[ i ] );
} else {
}
}
}
for( int x: dsctz ) if( ~x & 1 ) {
for( int y: dsctz ) if( y & 1 ) if( y != 1 ) {
if( not np[ x + y ] ) {
no_one.add_edge( id( x ), id( y ), no_one.INF );
has_one.add_edge( id( x ), id( y ), has_one.INF );
}
}
}
int sum = accumulate( ps.begin() + 2, ps.end(), 0 );
return max( sum - no_one.flow(), sum - bad1 + ps[ 1 ] - has_one.flow() );
}

signed main() {
for( int i = 2; i <= MAXC * 2; ++i ) {
if( np[ i ] ) continue;
for( int j = i + i; j <= MAXC * 2; j += i ) {
np[ j ] = 1;
}
}
ios::sync_with_stdio( 0 );
cin >> N >> K;
for( int i = 0; i < N; ++i ) {
cin >> P[ i ] >> C[ i ] >> L[ i ];
}
int lb = 0, ub = N + 1;
while( ub - lb > 1 ) {
int mid = lb + ub >> 1;
( score( mid ) < K ? lb : ub ) = mid;
}
cout << ( ub <= N ? ub : -1 ) << endl;
return 0;
}
```