AT_past201912_i 部品調達

[problemUrl]: https://atcoder.jp/contests/past201912-open/tasks/past201912_i あなたは、あるものを作るために $ 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 $ 個以上手に入れるのに必要な金額を求める (または、それが不可能であることを報告する) プログラムを作成せよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ S_1 $ $ C_1 $ $ S_2 $ $ C_2 $ $ : $ $ S_M $ $ C_M $

すべての部品を $ 1 $ 個以上手に入れることが可能であれば、それに必要な最小金額を表す整数を出力せよ。 そうでなければ、`-1` と出力せよ。

### 注意 この問題に対する言及は、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 $ がどのセットにも含まれておらず、すべての部品を揃えることは不可能である。