수식 고치기

T | F | T & F | T & F

위 식과 같이 값은 T와 F, 연산자는 |과 &로만 구성된 수식이 주어진다. | 연산은 양쪽에 있는 두 피연산자 중 하나 이상이 T이면 결괏값이 T이고, 그렇지 않으면 F이다. & 연산은 양쪽에 있는 두 피연산자가 모두 T이면 결괏값이 T이고, 그렇지 않으면 F이다. | 연산과 & 연산의 우선순위는 같고, 왼쪽부터 오른쪽으로 차례로 계산한다고 가정한다.

여러분은 연산자와 값을 적절히 바꾸어 원하는 계산 결과가 나오도록 해야 한다. 이때, 연산자와 값을 바꾸는 횟수를 최소화해야 한다. 식과 원하는 계산 결과가 주어졌을 때, 원하는 계산 결과가 나오도록 연산자와 값을 고치는 최소 횟수를 구하여라.

첫째 줄에 식에 있는 값의 개수와 연산자의 개수를 더한 정수 $N$이 주어진다.

둘째 줄에 $N$개의 문자 $A_1,A_2,\cdots ,A_N$이 공백으로 구분되어 주어진다. $i$가 홀수면 $A_i$는 값이고, $i$가 짝수면 $A_i$는 연산자이다.

셋째 줄에 원하는 계산 결과를 나타내는 문자 $C$가 주어진다.

원하는 계산 결과가 나오도록 값과 연산자를 고치는 최소 횟수를 출력하라.

• $1\le N\le 1\, 999$, $N$은 홀수
• $i$가 홀수면 $A_i\in\{$T, F$\}\ (1\le i\le N)$
• $i$가 짝수면 $A_i\in\{$&,|$\}\ (1\le i\le N)$
• $C\in\{$T, F$\}$