Minimum Replacement of Wildcards with '@'

You are given a pattern string and a target string. The pattern contains two kinds of wildcard characters: '?' and '*'. The matching rules are as follows:

• '?' matches any single character.
• '*' matches any sequence of characters (including the empty sequence).

You are allowed to modify the pattern by replacing some of the wildcard characters (i.e. '?' or '*') with the literal character '@'. In the modified pattern, the character '@' is treated as a normal character (that is, it only matches an '@' in the target string), whereas the other characters (letters, '?' and '*') follow the original matching rules. Your task is as follows:

1. First, determine if the original pattern matches the target string using the usual wildcard matching rules.
2. If it does match, choose a subset of the wildcard characters in the pattern to replace with '@' such that the modified pattern still matches the target string, and the total number of replacements is minimized.

If the original pattern does not match the target string, output -1. Otherwise, output the minimum number of wildcard replacements required. Note that when replacing a wildcard with '@', the corresponding character in the target string must be '@', because in the modified pattern, '@' is a literal character.

Note: Under the ordinary wildcard matching rules, a wildcard (either '?' or '*') can already match any character (including '@'). Therefore, it is always possible to match the target string without doing any replacements if the original matching holds. Hence, if the original pattern matches, the answer will be 0 unless a replacement is forced by a literal @ in the target string at a position where a wildcard must be replaced in order to guarantee the match under modified rules. In other words, you should compute the minimal number of replacements needed so that for every wildcard replaced by '@', the corresponding character in the target string is '@'.

It is guaranteed that if the original pattern matches the target string, then there is always an option of making 0 replacements (by leaving all wildcards unchanged), so the answer in that case is 0.

inputFormat

The input consists of two lines:

1. The first line contains the pattern string which may include lowercase/uppercase letters and the wildcard characters '?' and '*'.
2. The second line contains the target string.

outputFormat

Output a single integer:

• If the pattern does not match the target string under the usual wildcard matching rules, output -1.
• Otherwise, output the minimum number of wildcard characters that must be replaced by '@' so that the modified pattern still matches the target string.

sample

*a?b
xxaab

0