eolymp
bolt
Try our new interface for solving problems
Problems

Две строки

Две строки

Time limit 1 second
Memory limit 64 MiB

Заданы две строки 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
Source Orel STU & Udmurt SU Contest, Petrozavodsk, Thursday, September 1, 2005