警告
在日本标准时间 2019 年 12 月 29 日凌晨 05:00 之前请勿提及此问题。如有违反,可要求赔偿。
考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
你想买 N 制作某些物体的零件种类:零件 1, \ldots, N。网上搜索后发现 M 出售零件包。
的
树的 i第一个包 (1 \leq i \leq M) 由字符串描述 S_i 长度 N 和一个整数 C_i。的 j- 第一个字符 (1 \leq j \leq N) of S_i is Y 如果包装中包含零件 j,和 N 否则。该套装售价为 C_i 日元(日本的货币)。
编写一个程序,找出购买其中一些软件包并获得所有软件包所需的最低金额 N 种零件(或报告说这是不可能的)。获得多个同种零件是可以的。
约束
- 1 \leq N \leq 10
- 1 \leq M \leq 1000
- S_i 是一个长度为的字符串 N.
- 每个字符 S_i is
YorN. - 1 \leq C_i \leq 10^9
- C_i 是一个整数。
输入
输入由标准输入按以下格式给出:
N M S_1 C_1 S_2 C_2 : S_M C_M
输出
如果可以得到全部 N 种零件,打印代表这样做的最低金额的整数。
否则,打印 -1.
示例输入 1
3 4 YYY 100 YYN 20 YNY 10 NYY 25
示例输出 1
30
如果我们购买第二个和第三个包裹,我们会得到各种零件 1, 2, 3 为 20 + 10 = 30 日元。
示例输入 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