DuTub

면접 대비

시간 제한1초메모리 제한1024 MB

요약

길이와 최대 10개 범주 중 일부를 가진 N개의 영상이 주어질 때, 모든 범주를 포함하면서 총 재생 시간이 최소가 되는 부분집합을 고른다.

난이도: 보통10점 중 4점
유형: 비트 연산, 동적 계획법, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

이쯤이면 자야 한다는 걸 알지만, 자기 전에 DuTub을 조금만 더 보려고 한다.

관심 있는 카테고리가 여러 개 있다. DuTub의 각 영상은 하나 이상의 카테고리에 속할 수 있다. 자기 전에 각 카테고리마다 최소 한 개의 영상을 봐야 한다. 물론 필요 이상으로 늦게까지 깨어 있고 싶지는 않다.

영상 목록이 주어졌을 때, 모든 카테고리의 영상을 최소 하나씩 보기 위해 시청해야 하는 최소 시간을 계산하는 프로그램을 작성하라.

입력

첫째 줄에 영상의 개수 $N$ 이 주어진다 ( $1 \le N \le 30$ ). 다음 $N$ 개의 줄에 영상에 대한 정보가 주어진다. 각 줄은 먼저 정수 $d_i$ ( $1 \le d_i \le 900$ )가 주어지며 이는 영상의 길이(초)이고, 그다음에 영상이 속한 카테고리를 나타내는 문자열이 주어진다. 각 문자(a부터 j까지)는 하나의 카테고리를 나타낸다. 각 영상은 최소 하나의 카테고리에 속하며, 한 영상의 설명에서 카테고리는 중복되지 않는다. 서로 다른 카테고리는 최대 10개까지 있을 수 있다.

출력

모든 카테고리의 영상을 보기 위해 DuTub에서 보내야 하는 최소 시간(초)을 출력한다.

예제2

예제 1
입력
```
5
200 ei
150 e
10 g
50 gb
60 i
```
예상 출력
```
250
```

예제 2

입력

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

예상 출력