B - 謎のたこ焼きおじさん
Editorial
/
あなたはたこ焼きを買いに来たところ、伝説のたこ焼きマスター高橋社長に認められ、新しく作るたこ焼き屋さんの店長を任されました。
店長に任命されたあなたに与えられた最初の仕事は、お店の看板を作成することでした。
ところが高橋社長は使えない時間がないので、たこ焼き屋さんの名前は決めましたが、看板を作るのはあなたに任せて去って行きました。
その際に看板を作るための英字ブロックが入ったいくつかのキットを渡されました。
英字キットとは、ランダムな英字ブロックが含まれている袋のことです。
例えば英字キットを表す文字列が ABCC であるような英字キットの場合、
つまり、英字キット ABCC 1 袋につき、英字ブロック
高橋社長から渡された英字キットは全て同じ英字キットだったので、どのキットを開けても中身は全く同じです。
あなたは看板にお金をかけるわけにもいかないので、開封する英字キットを最小にして残りは返品したいです。
どれだけの英字キットを使うことで、お店の看板を作ることができるでしょうか。
入力は以下の形式で標準入力から与えられる。
看板をつくるために必要な英字キットの最小数を標準出力に 1 行で出力すること。
与えられた英字キットで看板を作成することができない場合は、
また、出力の最後には改行をいれること。
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
のみである。
- 文字列 name に含まれる文字は
- 3 行目には英字キットに含まれている英字ブロックを表す文字列 kit が M 文字で与えられる。
- 文字列 kit に含まれる文字は
A
-Z
のみである。
- 文字列 kit に含まれる文字は
出力
与えられた英字キットで看板を作成することができない場合は、
-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 では英字ブロック
C
H
K
U
D
A
I
が足りないため、お店の名前 CHOKUDAI を作成することができません。 - よって、
-1
を出力します。
入力例 4
6 6 MONAKA NAMAKO
出力例 4
1
- 英字キット NAMAKO に含まれる英字ブロック
N
A
M
A
K
O
を入れ替えると、お店の名前 MONAKA を作成することができます。