# Problem A

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 |