Два рядки

Задано два рядки a та b. Яку найменшу кількість символів потрібно видалити з кінця рядка a, щоб він зустрічався у рядку b не менше ніж k разів? Знайдені підрядки не повнні перетинатись. Вважається, що порожній рядок зустрічається у довільному рядку, у тому числі і у порожньому, нескінченну кількість разів.

Вхідні дані

У першому рядку вхідного файлу записано натуральне число k, а у наступних двох рядках файлу записано рядки a та b, довжини яких не більші 500000 символів. Рядки складаються з символів з кодами від 32 до 255, включно.

Вихідні дані

У якості відповіді вивести кількість символів, які потрібно видалити.

Приклади