/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
注意
この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。
試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
あなたは、あるものを作るために N 種類の部品、部品 1, \ldots, N を購入しようとしている。ネット通販サイトを探すと、部品のセット販売が M 件見つかった。
i 件目のセット販売 (1 \leqq i \leqq M) の情報は、長さ N の文字列 S_i と整数 C_i の組として与えられる。S_i の j 文字目 (1 \leqq j \leqq N) は、このセットが部品 j を含むとき Y、含まないとき N である。また、このセットは C_i 円で販売されている。
これらのセットのうち何個かを購入し、N 種類の部品をすべて 1 個以上手に入れるのに必要な金額を求める (または、それが不可能であることを報告する) プログラムを作成せよ。
制約
- 1 \leqq N \leqq 10
- 1 \leqq M \leqq 1,000
- S_i は長さ N の文字列である。
- S_i の各文字は
YまたはNである。 - 1 \leqq C_i \leqq 1,000,000,000
- C_i は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 C_1 S_2 C_2 : S_M C_M
出力
すべての部品を 1 個以上手に入れることが可能であれば、それに必要な最小金額を表す整数を出力せよ。
そうでなければ、-1 と出力せよ。
入力例 1
3 4 YYY 100 YYN 20 YNY 10 NYY 25
出力例 1
30
2 番目と 3 番目のセットを購入すると、20 + 10 = 30 円で部品 1, 2, 3 すべてが揃う。
入力例 2
5 4 YNNNN 10 NYNNN 10 NNYNN 10 NNNYN 10
出力例 2
-1
部品 5 がどのセットにも含まれておらず、すべての部品を揃えることは不可能である。
入力例 3
10 14 YNNYNNNYYN 774472905 YYNNNNNYYY 75967554 NNNNNNNNNN 829389188 NNNNYYNNNN 157257407 YNNYNNYNNN 233604939 NYYNNNNNYY 40099278 NNNNYNNNNN 599672237 NNNYNNNNYY 511018842 NNNYNNYNYN 883299962 NNNNNNNNYN 883093359 NNNNNYNYNY 54742561 NYNNYYYNNY 386272705 NNNNYYNNNN 565075143 NNYNYNNNYN 123300589
出力例 3
451747367
Warning
Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.
After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
You want to buy N kinds of parts to make some objects: Part 1, \ldots, N. After searching online, you found M packages of parts on sale.
The i-th package (1 \leq i \leq M) is described by a string S_i of length N and an integer C_i. The j-th character (1 \leq j \leq N) of S_i is Y if the package contains Part j, and N otherwise. This package is sold for C_i yen (the currency of Japan).
Write a program that finds the minimum amount of money needed to buy some of these packages and get all N kinds of parts (or reports that it is impossible). It is fine to get more than one part of the same kind.
Constraints
- 1 \leq N \leq 10
- 1 \leq M \leq 1000
- S_i is a string of length N.
- Each character of S_i is
YorN. - 1 \leq C_i \leq 10^9
- C_i is an integer.
Input
Input is given from Standard Input in the following format:
N M S_1 C_1 S_2 C_2 : S_M C_M
Output
If it is possible to get all N kinds of parts, print the integer representing the minimum amount of money to do so.
Otherwise, print -1.
Sample Input 1
3 4 YYY 100 YYN 20 YNY 10 NYY 25
Sample Output 1
30
If we buy the second and third packages, we get all kinds of parts 1, 2, 3 for 20 + 10 = 30 yen.
Sample Input 2
5 4 YNNNN 10 NYNNN 10 NNYNN 10 NNNYN 10
Sample Output 2
-1
Part 5 is not contained in any package, so we cannot get all kinds of parts.
Sample Input 3
10 14 YNNYNNNYYN 774472905 YYNNNNNYYY 75967554 NNNNNNNNNN 829389188 NNNNYYNNNN 157257407 YNNYNNYNNN 233604939 NYYNNNNNYY 40099278 NNNNYNNNNN 599672237 NNNYNNNNYY 511018842 NNNYNNYNYN 883299962 NNNNNNNNYN 883093359 NNNNNYNYNY 54742561 NYNNYYYNNY 386272705 NNNNYYNNNN 565075143 NNYNYNNNYN 123300589
Sample Output 3
451747367