팰린드롬 완성하기

문제 정보

문제

팰린드롬 만들기 대회 (Palindrome Creating Contest, PC^2)가 개최된다! 이 대회는 알파벳 소문자 'a'와 'b'로 구성된 팰린드롬들 중에서 어느 것이 가장 아름다운가를 겨루는 대회이다.

승현이는 PC^2에 출품하기 위해 'a'와 'b'로 구성된 길이가 N인 팰린드롬을 하나 만들었다. 승현이는 기쁜 마음으로 팰린드롬을 들고 집을 나서 대회장으로 향했다. 불운하게도, 승현이는 돌부리에 걸려 넘어져 팰린드롬의 일부를 망가뜨리고 말았다.

놀란 승현이는 일단 팰린드롬을 고치기로 마음먹고 집으로 돌아갔다. 승현이는 망가진 팰린드롬에서 온전한 부분을 제외한 나머지 부분을 모두 제거했다. 글자들은 틀에 끼어 있기 때문에, 한 글자를 제거하면 빈칸 하나가 생긴다. 빈칸이 있는 팰린드롬은 아름답지 않으므로, 승현이는 빈칸들을 'a' 또는 'b'로 적당히 채워 팰린드롬을 만들어야 한다. 문제는 글자들에 장식을 달아야 하므로, 'a'를 만드는 데 p분, 'b'를 만드는 데 q분이라는 막대한 시간이 걸린다는 것이다. 설상가상으로 승현이는 동시에 2개 이상의 글자를 만들 수 없다. 다행히도 글자를 만든 뒤 틀에 끼우는 데에는 시간이 들지 않는다.

승현이는 최소한의 시간을 들여 팰린드롬을 다시 완성하고자 한다. 여러분은 승현이의 망가진 팰린드롬과 p, q가 주어질 때, 승현이가 팰린드롬을 만들기 위해 들여야 할 최소한의 시간을 구하는 프로그램을 작성해야 한다.

입력

입력은 T개의 테스트 케이스들로 구성된다. 첫 번째 줄에 테스트 케이스의 수 T (1 \le T \le 200)가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 망가진 팰린드롬의 길이 N (1 \le N \le 1,000)이, 두 번째 줄에는 망가진 팰린드롬을 나타낸 문자열 S가 주어진다. S는 'a'(아스키 코드 97), 'b'(아스키 코드 98), '?'(아스키 코드 63)으로만 구성되어 있다. '?'는 빈 칸을 나타낸다. 세 번째 줄에는 'a'를 만드는 데 걸리는 시간 p와 'b'를 만드는 데 걸리는 시간 q (1 \le p, q \le 100)가 공백을 사이로 두고 분 단위로 주어진다.

출력

각 테스트 케이스마다 한 줄에 하나씩 망가진 팰린드롬을 팰린드롬으로 바꾸기 위해 드는 최소 시간을 분 단위로 출력한다. 불가능한 경우는 주어지지 않는다.

예제 입력

2
6
b???bb
1 3
1
?
1 2

예제 출력

5
1

노트

어떤 문자열 S = s_{1}s_{2}\cdots s_{n}이 팰린드롬이라는 것은 이것을 앞에서부터 뒤로 읽으나 뒤에서부터 앞으로 읽으나 동일하다는 것과 같다. 즉,

s_{1} s_{2} \cdots s_{n-1} s_{n} = s_{n} s_{n-1} \cdots s_{2} s_{1}

0개의 댓글이 있습니다.