← 返回题目列表

AtCoder · past201912_i

I. 采购

中文机器翻译题面 查看原题

警告

在日本标准时间 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 Y or N.
  • 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