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

Contest Duration: 2012-09-22(Sat) 11:00 - 2012-09-22(Sat) 12:30 (local time) (90 minutes) Back to Home

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を出力すること。
また、出力の最後には改行をいれること。

入力例 1Copy

Copy

7 26
NAOHIRO
ABCDEFGHIJKLMNOPQRSTUVWXYZ

出力例 1

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

入力例 2Copy

Copy

8 8
TAKOYAKI
TAKOYAKI

出力例 2

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

入力例 3Copy

Copy

8 4
CHOKUDAI
MYON

出力例 3

-1

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

入力例 4Copy

Copy

6 6
MONAKA
NAMAKO

出力例 4

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

Source Name

ARC 008