← 返回题目列表

AtCoder · arc008_2

B. 神秘的章鱼烧叔叔

中文机器翻译题面 查看原题

問題文

当你来买章鱼烧时,你得到了传说中的章鱼烧大师高桥社长的认可,并被任命为一家新章鱼烧店的经理。
被任命为店长后,给你的第一个任务是为商店制作招牌。
然而,高桥社长无法使用我没有太多时间,所以我决定了章鱼烧店的名称,但我把它留给你做标志然后离开了。
当时,我得到了几个包含字母块的套件来制作招牌。
字母套件是一个包含随机字母块的袋子。
例如,表示字母套件的字符串是 对于字母套件,例如 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 。