该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师喜欢数字x，最初他得到了一个数字字符串s，他可以对字符串进行操作：选择一部分字符串（可以是全部）并把它加到s的末尾，徐老师想知道他至少要操作多少次才能让s中x出现的次数不少于n，不可能则输出-1

Format

Input

第一行两个整数$n,x(0 \leq n \leq 10^9),(0 \leq x \leq 9)$，表示想要出现的次数和徐老师喜欢的数字

第二行给定一个字符串$s(1 \leq |s| \leq 10^5)$，表示初始字符串

Output

一个整数，表示至少出现的次数

Samples

1 1
1

0

Limitation

1s, 1024KiB for each test case.