# Poj Solution 3211

```http://poj.org/problem?id=3211

#include <stdio.h>
#include <vector>
#include <string>
#include <set>
using namespace std;

vector<int> v[10];
string color[10];
set<int> s;

int main( ) {
int n, m, i, j, ans, sum, t, best;
char w[100];
while( scanf( "%d%d", &m, &n ) == 2 && ( n || m ) ) {

for( i=0; i<m; i++ ) {
scanf( "%s", w );
color[i] = w;
v[i].clear( );
}

for( i=0; i<n; i++ ) {
scanf( "%d %s", &t, w );
for( j=0; j<m; j++ )
if( color[j] == w )
break;
v[j].push_back( t );
}

set<int>::reverse_iterator it;
ans = 0;

for( i=0; i<m; i++ ) {
s.clear();
s.insert( 0 );
sum = 0;

for( j=0; j<v[i].size(); j++ ) {
for( it = s.rbegin(); it != s.rend(); it++ ) {
if( s.find( t=*it+v[i][j] ) == s.end() )
s.insert( t );
}
sum += v[i][j];
}

best = sum;

for( it = s.rbegin(); it != s.rend(); it++ ) {
t = *it;
if( sum - t > t )
t = sum - t;
if( best > t )
best = t;
}
ans += best;
}

printf( "%dn", ans );
}
return 0;
}

```
This entry was posted in poj. Bookmark the permalink.