파충류 알

농장은 장식한 칠면조 알을 팔아 추가 수입을 얻는다. 농장주들은 창의성이 지나쳐서 여러 무늬를 설계하고 알 표면에 입힌다. 주문은 특별히 훈련된 파충류가 처리하며, 보통 코모도왕도마뱀이나 그와 비슷한 다른 파충류가 맡는다. 파충류는 정해진 형식 언어로 쓰인 명령을 이해하고 실행하도록 훈련되어 있다. 고객 주문은 파충류가 따를 명령으로 바뀌고, 파충류는 그 명령에 맞는 알 묶음을 생산 라인에서 고른다. 고른 알은 포장되어 배송을 준비한다.

명령은 정규 표현식이다. 파충류는 생산 라인에서 주어진 정규 표현식과 정확히 일치하는 알의 나열을 고른다. 고른 나열은 연속일 필요가 없고, 표현식으로 하나로 정해질 필요도 없다. 다만 고객을 만족시키려면 고른 나열은 항상 가능한 한 길어야 한다. 파충류는 생산 라인의 시작과 끝을 알고 있으므로, 고른 나열의 첫 알은 마지막 알보다 라인 끝에서 더 멀리 떨어져 있지 않다.

주문이 너무 까다로워서 빈 것이 아닌 어떤 알 나열도 표현식과 맞지 않을 수 있다. 이때도 파충류는 두 경우를 구별한다. 첫째, 알이 하나도 없는 빈 나열이 표현식과 맞을 수 있다. 둘째, 빈 나열도 표현식과 맞지 않는다. 첫 번째 경우에는 파충류가 차분하게 있지만, 두 번째 경우에는 몹시 화가 나서 진정시켜야 한다.

파충류의 동작을 확인하라. 주어진 정규 표현식마다, 출하할 수 있는 알 개수의 최댓값을 구하라.

표현식의 명세는 다음과 같다.

• 각 표현식은 영어 소문자와 ?, *, [, ], (, ) 문자로 이루어진 유한한 문자열이다.
• 영어 소문자 하나는 그 글자에 해당하는 무늬의 알 하나를 나타낸다.
• (?)는 어떤 무늬든 상관없는 알 하나를 나타낸다.
• 대괄호 [와 ]는 항상 짝이 맞고, 안에는 영어 소문자가 최소 하나 있다. 이 대괄호와 그 안의 글자는 알 하나를 나타내며, 그 알의 무늬는 안의 글자 중 어느 하나와도 맞는다.
• 별표 *는 바로 앞의 부분을 0번 이상 반복한다는 뜻이다. 바로 앞의 부분은 소문자 하나, 물음표, 또는 ()나 []로 묶인 표현식의 일부다. 반복 횟수는 0일 수도 있다.
• 괄호 (와 )는 항상 짝이 맞고, 바로 뒤에 별표가 온다. 괄호 안에는 위 규칙을 따르는 정규 표현식이 있지만, 그 안에 괄호는 없다.

첫 줄에 정수 $N$ ($1 \le N \le 1000$)이 주어진다. 둘째 줄에는 생산 라인 위 알의 무늬를 나타내는 길이 $N$의 영어 소문자 문자열이 주어진다. 첫 글자가 라인의 시작에 해당한다. 셋째 줄에 정수 $M$ ($1 \le M \le 1000$)이 주어진다. 넷째 줄에는 파충류에게 주어지는 길이 $M$의 정규 표현식 문자열이 주어진다.

주어진 정규 표현식에 따라 생산 라인에서 고를 수 있는 알의 최대 개수 $E$를 정수 하나로 출력하라. 정규 표현식과 일치시킬 수 없다면 -1을 출력하라.