Задача M. Укорачивание текста

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

По заданному тексту длины N и образцу длины K определить длину минимальной подстроки в тексте, которая удовлетворяет данному образцу. Текст состоит только из маленьких латинских букв. Образец содержит маленькие латинские буквы и символ '*', заменяющий любое множество любых символов(в том числе пустое).

Формат входного файла

В первой строке входного файла находятся два числа K и N, в следующих двух строках находятся соответственно образец и строка.

Формат выходного файла

В выходном файле должно находится единственное число — минимальная длина искомой подстроки, или  − 1, если образец в тексте не встречается.

Ограничения

1 ≤ N ≤ 1000000, 1 ≤ K ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 4
a*b
abab
2

0.087s 0.016s 15