У вас есть строка \(a\) и строка \(b\). Обе строки имеют длину \(n\). В строке \(a\) содержится не более \(10\) различных символов. У вас также есть множество \(Q\). Изначально множество \(Q\) пусто. Вы можете применить следующую операцию к строке \(a\) любое количество раз:
- Выберите индекс \(i\) (\(1\leq i \leq n\)) и строчный латинскую букву \(c\). Добавьте \(a_i\) в множество \(Q\) и замените \(a_i\) на \(c\).
Например, пусть строка \(a\) — это «\(\tt{abecca}\)». Мы можем выполнить следующие операции:
- В первой операции, если выбрать \(i = 3\) и \(c = \tt{x}\), символ \(a_3 = \tt{e}\) будет добавлен к множеству \(Q\). Таким образом, множество \(Q\) будет равняться \(\{\tt{e}\}\), а строка \(a\) станет «\(\tt{ab\underline{x}cca}\)».
- Во второй операции, если выбрать \(i = 6\) и \(c = \tt{s}\), то символ \(a_6 = \tt{a}\) будет добавлен к множеству \(Q\). Таким образом, множество \(Q\) будет равняться \(\{\tt{e}, \tt{a}\}\), а строка \(a\) будет «\(\tt{abxcc\underline{s}}\)».
Со строкой \(a\) можно выполнить любое количество операций, но в конце множество \(Q\) должно содержать не более \(k\) различных символов. Учитывая это ограничение, вам нужно максимизировать количество пар целых чисел \((l, r)\) (\(1\leq l\leq r \leq n\)) таких, что \(a[l,r] = b[l,r]\). Здесь \(s[l,r]\) означает подстроку строки \(s\), начинающуюся с индекса \(l\) (включительно) и заканчивающуюся индексом \(r\) (включительно).
Выходные данные
Для каждого набора входных данных выведите в строке одно целое число — максимальное количество пар \((l, r)\), удовлетворяющих ограничениям.
Примечание
В первом наборе входных данных мы можем выбрать индекс \(i = 3\) и заменить его символом \(c = \tt{d}\). Все возможные пары \((l,r)\) будут удовлетворять условию.
Во втором наборе мы не можем выполнить ни одну операцию. \(3\) удовлетворяющие условию пары \((l,r)\):
- \(a[1,1] = b[1,1] =\) «\(\tt{a}\)»,
- \(a[1,2] = b[1,2] =\) «\(\tt{ab}\)»,
- \(a[2,2] = b[2,2] =\) «\(\tt{b}\)».
В третьем наборе мы можем выбрать индекс \(2\) и индекс \(3\) и заменить их символами \(\tt{c}\) и \(\tt{d}\) соответственно. Множество \(Q\) в конце будет равняться \(\{\tt{b}\}\) (размер равен \(1\), не превышает \(k\)). Все возможные пары \((l,r)\) будут подходить под условие.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3 1
abc
abd
3 0
abc
abd
3 1
xbb
xcd
4 1
abcd
axcb
3 10
abc
abd
10 3
lkwhbahuqa
qoiujoncjb
|
6
3
6
6
6
11
|