Задачі
Хеш-функція Далла
Хеш-функція Далла
Професор Далл дуже полюбляє придумувати нові "хороші" хеш-функції для рядків. Нещодавно він опублікував статтю з описом наступного методу. Любимий рядок \textbf{W} вважається одним з параметрів алгоритма. Іншим параметром є деяке натуральне число \textbf{K}, яке не перевищує довжини рядка \textbf{W}. Хеш-функція рахується для рядка \textbf{S}. Спочатку у рядку \textbf{S} знаходяться усі такі його підрядки, які є анаграмами рядка \textbf{W}. З усіх цих анаграм обираються найбільший у змісті лексикографічного порядку рядок \textbf{A_1} та найменший - \textbf{A_2}. Далі для кожної пари підрядків довжини \textbf{K} з \textbf{A_1} та \textbf{A_2} рахується кількість однакових символів у однакових позиціях. Усі ці величини додаються - це і є шукане значення. Якщо у \textbf{S} немає підрядків, які є анаграмами \textbf{W}, значення хеш-функції вважається рівним \textbf{0}.
\textit{Підрядком} називається довільна послідовність символів заданого рядка, що йдуть підряд. \textit{Анаграма} - рядок, який отримується перестановкою букв заданого рядка.
\InputFile
У першому рядку вхідного файлу записано натуральне число \textbf{K}. У другому рядку записано рядок \textbf{W}. Його довжина - натуральне число, яке не перевищує \textbf{3000}. Число \textbf{K} не перевищує довжини рядка \textbf{W}. У третьому рядку вхідного файлу міститься рядок \textbf{S}. Його довжина - натуральне число, яке не перевищує \textbf{100000}. Гарантується, що кількість позицій рядка \textbf{S}, у яких починаються підрядки, які є анаграмами \textbf{W}, не перевищує \textbf{2000}. Усі рядки складаються лише з рядкових латинських букв.
\OutputFile
Виведіть шукане значення хеш-функції Далла.
\textit{\textbf{Пояснення до прикладу 1}}: Підрядки-анаграми - \textbf{bab}, \textbf{abb}, \textbf{bba} (у порядку появи). Найбільший - \textbf{bba}, найменший - \textbf{abb}. У кожному рядку усього \textbf{2} підрядки довжини \textbf{K = 2}. Кількістьо співпадінь у \textbf{bb} та \textbf{ab} - \textbf{1}, у \textbf{bb} та \textbf{bb} - \textbf{2}, у \textbf{ba} та \textbf{ab} - \textbf{0}, у \textbf{ba} та \textbf{bb} - \textbf{1}. Усього \textbf{4} співпадіння.
Вхідні дані #1
2 abb cababba
Вихідні дані #1
4