题目描述

农场通过生产装饰过的火鸡蛋来获得额外收入。农场主极富创造力，会设计各种图案，并把它们绘制在蛋的表面。

顾客的订单由一只经过特殊训练的爬行动物负责处理。它通常是一只科莫多巨蜥，也可能是其他合适的爬行动物。它已经学会理解并执行一种特定形式语言中的命令。

每份顾客订单都会被转换成一条命令。爬行动物根据命令，从生产线上选出相应的一组蛋，随后这些蛋会被包装并准备发货。

命令是一个正则表达式。爬行动物需要从生产线上选出一个序列，使该序列能够被给定正则表达式完整匹配。

被选出的蛋不必在生产线上连续，因此所选序列是原序列的一个子序列；但蛋的先后顺序必须与生产线上的顺序一致。

同一个正则表达式可能对应多种选法。为了让顾客满意，爬行动物总会选择长度尽可能大的序列。

有时，顾客给出的正则表达式过于苛刻，无法匹配任何非空序列。此时仍有两种不同情况：

1. 空序列可以被该正则表达式匹配；
2. 连空序列也不能被该正则表达式匹配。

第一种情况下，爬行动物会保持冷静；第二种情况下，它会变得非常恼怒，需要被安抚。

请检查爬行动物的操作，并求出根据给定正则表达式最多可以选出多少个蛋。

正则表达式规则

正则表达式由小写英文字母以及字符 ?、*、[、]、(、) 构成，并满足以下规则：

1. 每个小写英文字母表示一个具有对应图案的蛋。

2. 问号 ? 表示任意一种图案的一个蛋。

3. 方括号 [ 与 ] 一定正确配对。方括号内部只包含至少一个小写英文字母。

   整个方括号结构表示一个蛋，其图案可以是括号中列出的任意一个字母。

   例如，[abc] 可以匹配图案为 a、b 或 c 的一个蛋。

4. 星号 * 表示它前面的基本单元可以重复任意多次，重复次数也可以为 $0$。

   星号前面的基本单元只可能是以下四种之一：

   • 一个小写字母；
   • 一个问号 ?；
   • 一段由圆括号 (、) 包围的表达式；
   • 一段由方括号 [、] 包围的字符集合。

5. 圆括号 ( 与 ) 一定正确配对，并且每一对圆括号后面都紧跟一个星号 *。

   圆括号内部仍是符合上述规则的正则表达式，但其中不会再出现圆括号，也就是说圆括号不会嵌套。

输入格式

第一行包含一个整数 $N$（$1\le N\le 1000$）。

第二行包含一个长度为 $N$ 的小写字母字符串，表示生产线上每个蛋的图案。字符串开头对应生产线的起点，每个字符对应一个蛋。

第三行包含一个整数 $M$（$1\le M\le 1000$）。

第四行包含一个长度为 $M$ 的字符串，表示给爬行动物的正则表达式。

输出格式

输出一个整数 $E$，表示按照给定正则表达式，最多能够从生产线上选出的蛋的数量。

如果没有任何序列能够被该正则表达式匹配，连空序列也不行，则输出 -1。

因此，当正则表达式只能匹配空序列时，应输出 0。

样例 1

输入

3
aba
2
a*

输出

2

样例 2

输入

3
ctu
4
open

输出

-1

样例 3

输入

4
food
13
([ba]g??t*e)*

输出

0

样例 4

输入

20
alotofeggcellenteggs
14
[only]*(egg)*?

输出

10