Две строки

Заданы две строки a и b. Какое наименьшее количество символов следует удалить из конца строки a, чтобы она встречалась в строке b не менее чем k раз? Найденные подстроки не должны пересекаться. Считается, что пустая строка встречается в любой строке, в том числе и в пустой, бесконечное число раз.

Входные данные

В первой строке входного файла записано натуральное число k, а в следующих двух строках файла записаны строки a и b, длины которых не более 500000 символов. Строки состоят из символов с кодами от 32 до 255, включительно.

Выходные данные

В качестве ответа вывести количество символов, которые нужно удалить.

Примеры