B - 謎のたこ焼きおじさん Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

あなたはたこ焼きを買いに来たところ、伝説のたこ焼きマスター高橋社長に認められ、新しく作るたこ焼き屋さんの店長を任されました。
店長に任命されたあなたに与えられた最初の仕事は、お店の看板を作成することでした。
ところが高橋社長は使えない時間がないので、たこ焼き屋さんの名前は決めましたが、看板を作るのはあなたに任せて去って行きました。
その際に看板を作るための英字ブロックが入ったいくつかのキットを渡されました。
英字キットとは、ランダムな英字ブロックが含まれている袋のことです。
例えば英字キットを表す文字列が ABCC であるような英字キットの場合、
  • 英字ブロックAが1つ含まれている。
  • 英字ブロックBが1つ含まれている。
  • 英字ブロックCが2つ含まれている。
とみなすことができます。
つまり、英字キット ABCC 1 袋につき、英字ブロックAと英字ブロックBを1つずつ、英字ブロックCを2つを看板に用いることができます。
高橋社長から渡された英字キットは全て同じ英字キットだったので、どのキットを開けても中身は全く同じです。
あなたは看板にお金をかけるわけにもいかないので、開封する英字キットを最小にして残りは返品したいです。
どれだけの英字キットを使うことで、お店の看板を作ることができるでしょうか。

入力

入力は以下の形式で標準入力から与えられる。 
N M
name
kit
  • 入力は 3 行ある。
  • 1 行目にお店の名前の文字数 N\ (1≦N≦50) と、英字キット 1 袋に入ってる英字ブロックの数 M\ (1≦M≦50) が空白区切りで与えられる。
  • 2 行目にはお店の名前を表す文字列 name が N 文字で与えられる。
    • 文字列 name に含まれる文字は A-Z のみである。
  • 3 行目には英字キットに含まれている英字ブロックを表す文字列 kit が M 文字で与えられる。
    • 文字列 kit に含まれる文字は A-Z のみである。

出力

看板をつくるために必要な英字キットの最小数を標準出力に 1 行で出力すること。
与えられた英字キットで看板を作成することができない場合は、-1を出力すること。
また、出力の最後には改行をいれること。

入力例 1

7 26
NAOHIRO
ABCDEFGHIJKLMNOPQRSTUVWXYZ

出力例 1

2
  • 英字キット ABCDEFGHIJKLMNOPQRSTUVWXYZ には英字ブロックOが 1 つしかないため、お店の名前 NAOHIRO を作成するためには英字キットを 2 袋用いる必要があります。

入力例 2

8 8
TAKOYAKI
TAKOYAKI

出力例 2

1
  • 英字キット TAKOYAKI を 1 袋用いると、お店の名前 TAKOYAKI を作成することができます。

入力例 3

8 4
CHOKUDAI
MYON

出力例 3

-1
  • 英字キット MYON では英字ブロックCHKUDAIが足りないため、お店の名前 CHOKUDAI を作成することができません。
  • よって、-1を出力します。

入力例 4

6 6
MONAKA
NAMAKO

出力例 4

1
  • 英字キット NAMAKO に含まれる英字ブロックNAMAKOを入れ替えると、お店の名前 MONAKA を作成することができます。

Source Name

ARC 008