[ARC008B] 謎のたこ焼きおじさん
题意翻译
## 题目描述
你来买章鱼烧的时候,得到了传说中的章鱼烧大师——章鱼烧店的老板高桥先生的认可,被任命为新的章鱼烧店的老板。
你被任命为店长后的第一份工作就是制作店铺的招牌。
现在章鱼烧店的名字已经决定好了,制作招牌的任务就交给了你。
因此这时候高桥老板就给了你几个制作招牌要用的英文字母配件包。
英文字母配件包指的是含有随机英文字母的袋子。
例如:当英文字母配件包表示为字符串ABCC的时候可以被认作是:
- 包含1个英文字母A
- 1个英文字母B
- 和2个英文字母C
也就是说,对于一袋英文配件包ABCC,1个英文字母A、1个英文字母B和2个英文字母C都可以被用于制作招牌。
因为从高桥老板那里得到的英文字母配件包都是相同的,所以打开任何一个英文字母配件包里面的东西也都是一样的。
你不想在制作招牌上花太多的钱,因此要使用尽量少的英文字母配件包,并把剩下的退货。
究竟用多少的英文字母配件包就可以完成招牌的制作呢?
## 输入输出格式
### 输入格式:
标准输入如下:
N M
name
kit
- 输入有3行
- 第一行为名字包含的英文字母个数N(1≦N≦50)和每一袋配件包含的英文字母个数M(1≦M≦50),以空格隔开
- 第二行为店名,一共N个字母,其中包含的字母只有A-Z
- 第三行为配件内所含的所有英文字母的字符串,一共M个字母,其中包含的字母只有A-Z
### 输出格式:
1行:制作招牌所需要的最少配件包数
如果所给的配件包无法制作招牌,则输出-1
另外,在输出的最后需要换行
## 说明:
- 样例1:因为英文字母配件包ABCDEFGHIJKLMNOPQRSTUVWXYZ内只含有一个O,因此制作招牌NAOHIRO需要两个配件包。
- 样例2:只用一个配件包TAKOYAKI就可以制作完成招牌TAKOYAKI。
- 样例3:英文字母配件包MYON内没有英文字母C,H,K,U,D,A,I,因此无法成功制作招牌。所以输出-1。
- 样例4:替换一下英文字母配件包NAMAKO内的字母顺序,便正好可以制作招牌。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc008/tasks/arc008_2
あなたはたこ焼きを買いに来たところ、伝説のたこ焼きマスター高橋社長に認められ、新しく作るたこ焼き屋さんの店長を任されました。
店長に任命されたあなたに与えられた最初の仕事は、お店の看板を作成することでした。
ところが高橋社長は使えない時間がないので、たこ焼き屋さんの名前は決めましたが、看板を作るのはあなたに任せて去って行きました。
その際に看板を作るための英字ブロックが入ったいくつかのキットを渡されました。
英字キットとは、ランダムな英字ブロックが含まれている袋のことです。
例えば英字キットを表す文字列が $ 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`を出力すること。
また、出力の最後には改行をいれること。 ```
2
```
- 英字キット $ ABCDEFGHIJKLMNOPQRSTUVWXYZ $ には英字ブロック`O`が $ 1 $ つしかないため、お店の名前 $ NAOHIRO $ を作成するためには英字キットを $ 2 $ 袋用いる必要があります。
```
1
```
- 英字キット $ TAKOYAKI $ を $ 1 $ 袋用いると、お店の名前 $ TAKOYAKI $ を作成することができます。
```
-1
```
- 英字キット $ MYON $ では英字ブロック`C``H``K``U``D``A``I`が足りないため、お店の名前 $ CHOKUDAI $ を作成することができません。
- よって、`-1`を出力します。
```
1
```
- 英字キット $ NAMAKO $ に含まれる英字ブロック`N``A``M``A``K``O`を入れ替えると、お店の名前 $ MONAKA $ を作成することができます。