AT_past201912_i 部品調達

有 $m$ 个数列，对于每个数列，给出一个长为 $n$ 的字符串 $s_i$ 表示 $1$ 到 $n$ 之间的整数是否在第 $i$ 个数列中出现了（用`Y`表示“是”，用`N`表示“否”；字符串下标从 $1$ 开始）。每个数列都有一个选择的代价 $c_i$。 请选择若干个数列，使得将这些数列拼接后，$1$ 到 $n$ 之间的每一个整数都在拼接后的数列中出现。输出所选择的数列的代价之和的最小值。

第一行为两个整数 $n$ 和 $m$。 接下来 $m$ 行，每行一个长为 $n$ 且仅含`Y`和`N`的字符串 $s_i$ 以及选择代价 $c_i$。

若目标可达成，请输出最小代价之和；否则，输出`-1`。 ### 数据规模与约定 $1 \le n \le 10$，$1 \le m \le 1000$，$1 \le c_i \le 10^9$，上述数值均为整数。

### 注意 この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 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 $ は整数である。 ### Sample Explanation 1 $ 2 $ 番目と $ 3 $ 番目のセットを購入すると、$ 20\ +\ 10\ =\ 30 $ 円で部品 $ 1,\ 2,\ 3 $ すべてが揃う。 ### Sample Explanation 2 部品 $ 5 $ がどのセットにも含まれておらず、すべての部品を揃えることは不可能である。