# CFR 321 B. Ciel and Duel ( DP )

Problem - B - Codeforces

The first line contains two integers n and m (1 ≤ n, m ≤ 100) — the number of cards Jiro and Ciel have.
Each of the next n lines contains a string position and an integer strength (0 ≤ strength ≤ 8000) — the position and strength of Jiro's current card. Position is the string "ATK" for attack, and the string "DEF" for defense.
Each of the next m lines contains an integer strength (0 ≤ strength ≤ 8000) — the strength of Ciel's current card.
TL: 2000 ms
ML: 256 MB

O( N^2 * M )

```int N, M;
vs mode; vi lp_strength;
vi fp_strength;

void init(){
cin >> N >> M;
mode = vs( N );
lp_strength = vi( N );
for( int i = 0; i < N; ++i ){
cin >> mode[ i ] >> lp_strength[ i ];
}
fp_strength = vi( M );
for( int i = 0; i < M; ++i ){
cin >> fp_strength[ i ];
}
}

vvvvi dp;
vi lp_atk_strength;
vi lp_def_strength;

void preprocess(){
for( int i = 0; i < N; ++i ){
if( mode[ i ] == "ATK" ){
lp_atk_strength.emplace_back( lp_strength[ i ] );
} else{
lp_def_strength.emplace_back( lp_strength[ i ] );
}
}
sort( lp_atk_strength.begin(), lp_atk_strength.end() );
sort( lp_def_strength.begin(), lp_def_strength.end() );
sort( fp_strength.begin(), fp_strength.end() );
dp = vvvvi( fp_strength.size() + 1, vvvi( lp_atk_strength.size() + 1, vvi( lp_def_strength.size() + 1, vi( 2, -INF ) ) ) );
dp[ 0 ][ 0 ][ 0 ][ 0 ] = 0;
for( int i = 0; i < fp_strength.size(); ++i ){
for( int j = 0; j <= lp_atk_strength.size(); ++j ){
for( int k = 0; k <= lp_def_strength.size(); ++k ){
for( int l = 0; l < 2; ++l ){
upmax( dp[ i + 1 ][ j ][ k ][ l ], dp[ i ][ j ][ k ][ l ] );
upmax( dp[ i + 1 ][ j ][ k ][ 1 ], dp[ i ][ j ][ k ][ l ] + fp_strength[ i ] );
if( j + 1 <= lp_atk_strength.size() ){
if( fp_strength[ i ] >= lp_atk_strength[ j ] ){
upmax( dp[ i + 1 ][ j + 1 ][ k ][ l ], dp[ i ][ j ][ k ][ l ] + fp_strength[ i ] - lp_atk_strength[ j ] );
}
}
if( k + 1 <= lp_def_strength.size() ){
if( fp_strength[ i ] > lp_def_strength[ k ] ){
upmax( dp[ i + 1 ][ j ][ k + 1 ][ l ], dp[ i ][ j ][ k ][ l ] );
}
}
}
}
}
}
}

void solve(){
int ans = dp[ fp_strength.size() ][ lp_atk_strength.size() ][ lp_def_strength.size() ][ 1 ]; // 全部殺した
for( int i = 0; i <= lp_atk_strength.size(); ++i ){
for( int j = 0; j <= lp_def_strength.size(); ++j ){
upmax( ans, dp[ fp_strength.size() ][ i ][ j ][ 0 ] );
}
}
cout << ans << endl;
}
```