DuTub

Interview

Time limit1sMemory limit1024 MB

Summary

Given N videos, each with a length and a set of categories among at most 10, choose a subset that covers every category while minimizing total length.

Level: Medium4 of 10
Topics: Bit manipulation, Dynamic programming, Brute force, Implementation
Solved: No attempts yet

Problem

You know you should go to bed at this point. But you are just going to watch a little more DuTub before going to sleep.

There are several categories you are interested in. Each video on DuTub can belong to one or more categories. Before you go to bed, you must have watched at least one video in every category. Of course, you do not want to stay up longer than necessary.

Write a program that, given a list of videos, computes the minimum possible time you have to watch to have seen at least one video from every category.

Input

The first line contains the number of videos $N$ ( $1 \le N \le 30$ ). Then follow $N$ lines describing the videos. Each of these lines first contains an integer $d_i$ ( $1 \le d_i \le 900$ ), the length of the video in seconds, followed by a string indicating the categories the video belongs to. Each letter (between a and j) denotes a category. Each video belongs to at least one category, and no categories are repeated in a video's description. There can be at most 10 different categories in total.

Output

The program shall print the minimum number of seconds you need to spend on DuTub before you have seen videos from all categories.

Examples2

Example 1
Input
```
5
200 ei
150 e
10 g
50 gb
60 i
```
Expected output
```
250
```

Example 2

Input

6
268 abe
271 ca
262 da
145 cd
150 ebc
143 deb

Expected output