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