D - Separation and Union

※この問題で Python 言語を用いる方は極力、提供されている Python 言語のコンパイル種類である pypy を選んで提出してください。CPython を選んで提出すると、実装方法によっては TLE になる可能性があります。

Story

🥞

matcharate君のおかげで、この世界で最も美しい看板メニュー名ができました。次はこのメニューを考えてみます。

センスのいいmatcharate君は、抹茶粉をふんだんに使ったパンケーキはどうだろう？と思いました。これには流石のtearate君でも感心しました。
とても協力的になったtearate君は、まずはmatcharate君が欲しい文字列チョコレートを作るために、たくさんの文字が書かれたチョコレートを買い直してきました。しかしmatcharate君の要望に答えるためには、いくつか文字が足りなかったようです。

流石にもう一度買いなおすと、今度はお店の経営資金に響いてしまいます。そこでtearate君は買いなおしたチョコレートから適切に分割させ、それらを組み合わせたチョコレートを新たに作ろうとしました。

問題

キッチンテーブルの上に $N$ 個の大きなチョコレートが横一列に置かれています。
左から数えて $i\ (1\le i\le N)$ 番目のチョコレートには $T_i$ という文字列が書かれています。

今からtearate君はテーブルに置かれたチョコレートをいくつか選び取り、さらにそれを $1$ 文字単位に分割し、文字が書かれた分割したチョコレートをいくつか選び取り、それらを適当に組み合わせて新たに文字列 $S$ が書かれたチョコレートを作りたいと思ってるようです。

最小でいくつのチョコレートを選べば良いですか？ただしどのように選んでも $S$ を作ることができないなら、その旨を報告してください。

入力

入力は以下の形式で与えられる。

制約

• $1\le N\le 16$、$N$ は整数
• $S,T_i$ の長さはそれぞれ $1$ 以上 $100$ 以下である
• $S,T_i$ は英小文字からなる

出力

答えを出力せよ。ただし全ての文字列を選んだとしても $S$ を作ることができないなら -1 を出力せよ。

入出力例

tearate
4
matcha rates sakura contest

3

例えば $T_1$ から $2$ 文字目、$T_2$ から $1,2,3,4$ 文字目、$T_4$ から $4,5$ 文字目を選んで切り出すことでそれぞれ a, r, a, t, e, t, e の文字が書かれたチョコレートが得られ、これらを組み合わせることで $S=$ tearate を作ることができます。$2$ つ以下の文字列だけ選んで作ることはできません。

matcharate
4
tea rates sakura contest

-1

全てを選んだとしても m, h の $2$ 文字が足りていないので作ることはできません。

matcha
4
matcha rates sakura contest

1

同じ文字列なら、$1$ つだけ選べばそれが良い選び方です。

matcharate
8
thanks for coming to resting place of tea

5