※この問題で 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