루미 알고리즘

#1457실버MeTube

PO 2018 학교 예선코딩출제 Arash Rouhani영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

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 (1 ≤ N ≤ 30).

This is followed by N lines describing the videos. Each video is described first by an integer d_i (1 ≤ d_i ≤ 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.

GroupPointsConstraints
120N ≤ 10, each video belongs to only one category.
240N ≤ 10
340No 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.

예제

예제 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
출력
412

출처 표기

출처: Programmeringsolympiaden 2018년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.