在森林里正常散步时,凯蒂偶然发现了一个神秘的代码!然而,神秘的代码中有些字符无法辨认。她将此代码写为字符串 $$$c$$$,由小写英文字符和星号 (“*”) 组成,其中每个星号表示一个不可读的字符。凯蒂对她的发现感到兴奋,她决定通过用任意小写英文字母替换每个星号来恢复不可读的字符(不同的星号可能会替换为不同的字母)。
Katie 有一个最喜欢的字符串 $$$s$$$ 和一个不太喜欢的字符串 $$$t$$$,她很想恢复神秘的代码,以便它尽可能多地出现 $$$s$$$ 并尽可能少地出现 $$$t$$$。正式地,我们将 $$$f(x, y)$$$ 表示为 $$$y$$$ 在 $$$x$$$ 中出现的次数(例如,$$$f(aababa, ab) = 2$$$)。 Katie 想要恢复符合原始 $$$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)$$$ 的最大可能值。
示例
输入 #1
***** katie shiro
输出 #1
1
输入 #2
caat caat a
输出 #2
-1
输入 #3
*a* bba b
输出 #3
0
输入#4
*** cc z
输出#4
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$$$。