D. Таинственный код
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Гуляя по лесу, Кэти наткнулась на таинственный код! Однако некоторые символы, к сожалению, оказались нечитаемыми. Кэти записала таинственный код как строку $$$c$$$, состоящую из строчных латинских букв и звёздочек («*»), где звёздочка обозначает нечитаемый символ. Вдохновлённая своим открытием, Кэти хочет восстановить нечитаемые символы, заменив каждую звёздочку произвольной строчной латинской буквой (разные звёздочки можно заменить на разные буквы).

Также у Кэти есть любимая строка $$$s$$$ и не очень любимая строка $$$t$$$. Она хочет восстановить таинственный код таким образом, чтобы количество вхождений $$$s$$$ в него было как можно больше, а количество вхождений $$$t$$$ как можно меньше. Формально, обозначим $$$f(x, y)$$$ как количество вхождений строки $$$y$$$ в строку $$$x$$$ (например, $$$f(aababa, ab) = 2$$$). Кэти хочет восстановить код $$$c'$$$, подходящий под изначальный код $$$c$$$, такой что $$$f(c', s) - f(c', t)$$$ является максимально возможной. Кэти не очень хороша в восстановлении кодов, поэтому она хочет, чтобы вы ей помогли.

Входные данные

Первая строка содержит строку $$$c$$$ ($$$1 \leq |c| \leq 1000$$$) — таинственный код. Гарантируется, что строка $$$c$$$ состоит только из строчных латинских букв и звёздочек «*».

Вторая и третья строка содержат строки $$$s$$$ и $$$t$$$ соответственно ($$$1 \leq |s|, |t| \leq 50$$$, $$$s \neq t$$$). Гарантируется, что строки $$$s$$$ и $$$t$$$ состоят только из строчных латинских букв.

Выходные данные

Выведите одно целое число — максимальное значение $$$f(c', s) - f(c', t)$$$ у восстановленного кода.

Примеры
Входные данные
*****
katie
shiro
Выходные данные
1
Входные данные
caat
caat
a
Выходные данные
-1
Входные данные
*a*
bba
b
Выходные данные
0
Входные данные
***
cc
z
Выходные данные
2
Примечание

В первом примере для $$$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$$$.