Problem G
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 |
