Гуляя по лесу, Кэти наткнулась на таинственный код! Однако некоторые символы, к сожалению, оказались нечитаемыми. Кэти записала таинственный код как строку \(c\), состоящую из строчных латинских букв и звёздочек («*»), где звёздочка обозначает нечитаемый символ. Вдохновлённая своим открытием, Кэти хочет восстановить нечитаемые символы, заменив каждую звёздочку произвольной строчной латинской буквой (разные звёздочки можно заменить на разные буквы).
Также у Кэти есть любимая строка \(s\) и не очень любимая строка \(t\). Она хочет восстановить таинственный код таким образом, чтобы количество вхождений \(s\) в него было как можно больше, а количество вхождений \(t\) как можно меньше. Формально, обозначим \(f(x, y)\) как количество вхождений строки \(y\) в строку \(x\) (например, \(f(aababa, ab) = 2\)). Кэти хочет восстановить код \(c'\), подходящий под изначальный код \(c\), такой что \(f(c', s) - f(c', t)\) является максимально возможной. Кэти не очень хороша в восстановлении кодов, поэтому она хочет, чтобы вы ей помогли.
Выходные данные
Выведите одно целое число — максимальное значение \(f(c', s) - f(c', t)\) у восстановленного кода.
Примечание
В первом примере для \(c'\) равной «katie», \(f(c', s) = 1\) и \(f(c', t) = 0\), тем самым \(f(c', s) - f(c', t) = 1\), что является наибольшим возможным значением.
Во втором примере есть лишь одна \(c'\) подходящая под исходный код \(c\): «caat». Соответствующая \(f(c', s) - f(c', t) = 1 - 2 = -1\).
В третьем примере есть несколько способов восстановить код, так чтобы \(f(c', s) - f(c', t)\) была максимально возможной, например «aaa», «aac», или «zaz». Величина \(f(c', s) - f(c', t) = 0\) для всех этих способов.
В четвёртом примере оптимальным способом восстановить \(c'\) является «ccc». В этом случае \(f(c', s) - f(c', t) = 2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
*****
katie
shiro
|
1
|
|
2
|
caat
caat
a
|
-1
|
|
3
|
*a*
bba
b
|
0
|
|
4
|
***
cc
z
|
2
|