50058. Word Selection

I'm a slow walker, but I never walk backwards.

Task Description

Given a set of $N$ words of lowercase letters, find the subset that has all 26 letters and the minimum cost. For example, if you are given abcdefghijklmnopqrst with cost 3, rstuvwxyz with cost 100, uvwxyzac with cost 10, and abcdefghijklmnopq with cost 1000, then the answer is 13. It is guaranteed that there will always be a set of solution that covers all 26 letters.

Hint

You can use an array of length 26 to keep track of the number of times each letter appears within the subset you selected.

Input Format

The first line in input is an integer $N$ indicating the number of words. For the following $N$ lines, each line contains a string and an integer indicating a word and its cost.

  • $0 \lt N \leq 20$
  • $0 \lt \textit{Word length} \leq 50$
  • $0 \lt \textit{cost} \lt 2147483647 $
  • $\textit{Sum of all costs} \lt 2147483647$

Output Format

There is one line in the output. The line has an integer indicating the minimum cost.

Sample Input 1

1
2
3
4
5
4
abcdefghijklmnopqrst 3
rstuvwxyz 100
uvwxyzac 10
abcdefghijklmnopq 1000

Sample Input 1

1
13

Discussion