Reptile Eggs

The farm earns extra income by selling decorated turkey eggs. The farmers are very creative, so they design many patterns and apply them to the egg surfaces. Orders are handled by a specially trained reptile, often a Komodo dragon or another suitable reptile species. The reptile is trained to understand and execute commands written in a specific formal language. A customer order is translated into a command for the reptile, and the reptile selects the matching group of eggs from the production line. The selected eggs are then packed and prepared for shipment.

The command is a regular expression. The reptile selects a sequence of eggs on the line that exactly matches the given regular expression. The selected sequence does not have to be contiguous, and it does not have to be uniquely determined by the expression. However, to keep customers satisfied, the selected sequence must always be as long as possible. The reptile recognizes the beginning and the end of the production line, so the first selected egg is not farther from the end of the line than the last selected egg.

Sometimes the order is so demanding that no nonempty sequence of eggs matches the expression. The reptile can still tell two cases apart. In the first case, an empty sequence (no eggs) matches the expression. In the second case, even the empty sequence does not match. In the first case the reptile stays calm. In the second case the reptile becomes dangerously annoyed and must be calmed down.

Check the reptile's operation. For each given regular expression, determine the maximum possible number of eggs in the shipment.

The expression specification is as follows.

• Each expression is a finite sequence of lowercase English letters and the characters ?, *, [, ], (, ).
• Each letter represents one egg with the pattern for that letter.
• The question mark (?) represents one egg with any pattern.
• The brackets [ and ] are always paired correctly. Inside them there is at least one lowercase letter. The brackets and the letters inside them represent a single egg whose pattern matches any of the letters inside.
• The asterisk * repeats the item immediately before it any number of times, including zero. That item is a single letter, a question mark, or a part of the expression enclosed in () or [].
• Parentheses ( and ) are always paired correctly and are always immediately followed by an asterisk. The parentheses contain a regular expression that follows these rules but contains no other parentheses.

The first line contains an integer $N$ ($1 \le N \le 1000$). The second line contains a string of $N$ lowercase English letters, the egg patterns on the production line. The first character corresponds to the beginning of the line. The third line contains an integer $M$ ($1 \le M \le 1000$). The fourth line contains a string of $M$ characters, the regular expression given to the reptile.

Print a single integer $E$, the maximum number of eggs in the shipment selected from the production line according to the given regular expression. If the regular expression cannot be matched, print -1.