Problems
Две строки
Две строки
Заданы две строки a и b. Какое наименьшее количество символов следует удалить из конца строки a, чтобы она встречалась в строке b не менее чем k раз? Найденные подстроки не должны пересекаться. Считается, что пустая строка встречается в любой строке, в том числе и в пустой, бесконечное число раз.
Input data
В первой строке входного файла записано натуральное число k, а в следующих двух строках файла записаны строки a и b, длины которых не более 500000 символов. Строки состоят из символов с кодами от 32 до 255, включительно.
Output data
В качестве ответа вывести количество символов, которые нужно удалить.
Examples
Input example #1
2 cabcabcde abcabcabc
Output example #1
6