D - Separation and Union

2 secs 1024 MB
matcharate12

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

Story


🥞

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

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

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

問題


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

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

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

入力


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



制約


  • は整数
  • の長さはそれぞれ 以上 以下である
  • は英小文字からなる

出力


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

入出力例


入力例1
tearate
4
matcha rates sakura contest
出力例1
3

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

入力例2
matcharate
4
tea rates sakura contest
出力例2
-1

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

入力例3
matcha
4
matcha rates sakura contest
出力例3
1

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

入力例4
matcharate
8
thanks for coming to resting place of tea
出力例4
5

提出


Go (1.14)