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