Hide

Problem B
MeTube

Languages en sv

You know that you should be sleeping by now... but you are going to just watch some more MeTube before going to bed.

On MeTube, there are number of categories you are interested in. Each video on MeTube can belong to one or more categories. Before going to bed, you must have watched one video in each category. Of course you don’t want to be up for longer than necessary.

Write a program that, given a list of videos, computes the smallest possible time you must stay up to have seen at least one video from each category.

Input

The first line contains the number of videos $N$ ($N \le 30$).

This is followed by $N$ lines describing the videos. Each video is described first by an integer $d_ i$ ($1 \le d_ i \le 900$), the length of the video in seconds, and then by a string with the categories that the video belongs to. In the string, each letter (between a and j) denotes one category. Each video belongs to at least one category and no category appears twice in the list for a video.

Output

Output the smallest number of seconds you need to spend on MeTube to watch a video from each category.

Scoring

Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.

Group

Points

Constraints

$1$

$20$

$N \le 10$, each video belongs to only one category.

$2$

$40$

$N \le 10$

$3$

$40$

No further constraints.

Explanation of sample 1

There are four categories: e, i, g, b. Watching the third video (g) is pointless since you must watch the fourth video (gb), since that’s the only one in category b. We prefer video $1$ over videos $2$ and $5$, since its total time is shorter and covers both categories i and e. The answer is $250$ seconds, by watching the first and fourth videos.

Sample Input 1 Sample Output 1
5
200 ei
150 e
10 g
50 gb
60 i
250
Sample Input 2 Sample Output 2
6
268 abe
271 ca
262 da
145 cd
150 ebc
143 deb
412