Where Have You Bin?

Ben Bean은 Ben Bean’s Bin Bonanza를 운영하며 마을의 다섯 큰 회사에 보관용 빈을 제공한다. 그 회사들은 고무줄 회사, Mercedes Benz 대리점, 빙 체리 농장, 봉봉 사탕 가게, 번 빵집이다. 이들은 각자의 고무줄, Benz, 빙 체리, 봉봉, 번을 Ben의 빈에 보관한다.

Ben에게는 한 줄로 늘어선 n개의 빈이 있고, 1번부터 n번까지 번호가 붙어 있다. 어떤 시점에 모든 빈이 사용 중인 것은 아니지만, Ben은 한 회사의 빈을 모두 연속해 두는 것이 편리하다고 생각한다. 따라서 어떤 회사가 새 빈을 필요로 하거나 더 이상 필요 없는 빈을 반납하면, Ben은 그 회사의 빈이 모두 서로 인접하도록 유지하기 위해 한 빈에서 다른 빈으로 물건을 옮겨야 할 수도 있다. 어느 빈을 옮길지 선택할 수 있을 때도 있으므로, Ben은 각 빈에 그 빈에 보관된 물건의 개수와 같은 비용을 매겼다. 반납한 빈에서 물건을 빼거나 새 빈으로 물건을 넣는 일은 회사의 책임이며 Ben의 비용에는 더해지지 않는다. 당연히 Ben은 빈을 옮길 때 비용을 최소로 유지하려 한다.

한 회사만 변경하는 경우 Ben은 보통 물건을 옮기는 가장 저렴한 방법을 알아낼 수 있지만, 보통 분기 말마다 다섯 회사 모두가 제품 구성을 재검토하면서 빈을 추가하거나 삭제한다. 이런 경우에는 최소 비용의 이동 집합을 결정하기가 더 어렵다. Figure K.1a는 다섯 회사 A, E, I, O, U의 물건을 담은 6개의 빈을 보여준다. 괄호 안의 숫자는 그 빈에 있는 물건의 개수이며, 따라서 그 빈의 물건을 다른 곳으로 옮길 때의 비용이다. 분기 말에 회사 U가 6번 빈이 더 이상 필요 없다고 결정하고 회사 A가 두 번째 빈을 요청한다고 하자. 한 가지 방법은 E의 물건을 2번 빈에서 비어 있는 6번 빈으로 옮겨 2번 빈을 회사 A에게 내주는 것이다(Figure K.1b). 이 재배치의 비용은 Ben에게 4이다. 그러나 최적의 이동은 U의 물건을 5번 빈에서 1번 빈으로 옮기고 A의 물건을 1번 빈에서 5번 빈으로 옮긴 뒤 회사 A에게 6번 빈을 주는 것이다(Figure K.1c). 이 이동의 비용은 3이다. Ben은 A의 물건을 1번 빈에서 6번 빈으로 옮겨 같은 최적 비용을 얻을 수도 있었다. 모든 경우에 U의 6번 빈에서 물건 세 개를 빼고 A의 두 번째 빈에 물건 일곱 개를 넣는 데는 Ben에게 비용이 들지 않는다.

Figure K.1: Sample Input 1.

입력은 빈의 초기 사용 상태를 나타내는 길이 n의 문자열로 시작한다(1 ≤ n ≤ 150). 문자는 모두 {A, E, I, O, U, X}에 속하며, 각 문자는 그 빈을 사용하는 회사 또는 빈 빈(X)을 나타낸다. 그다음 줄에는 각 빈에 있는 물건의 개수를 나타내는 n개의 정수가 온다. 빈 빈에 해당하는 위치의 값은 항상 0이고, 회사의 빈에 해당하는 위치의 값은 양수이며 100 이하이다. 한 회사의 빈은 항상 연속해 있다.

다음 줄은 이번 분기의 삭제 횟수를 나타내는 정수 d(0 ≤ d ≤ n)로 시작한다. 그 뒤에 d개의 정수가 온다. 각 정수는 어떤 회사가 더 이상 필요로 하지 않는 빈을 지정한다. 이미 빈 빈을 가리키는 경우는 없다. 마지막 줄에는 새로 요청하는 빈을 나타내는 양의 길이 문자열이 온다. 이 문자열이 X 하나라면 새로 요청하는 빈이 없다는 뜻이다. 그렇지 않으면 문자는 모두 {A, E, I, O, U}에 속하며 순서는 상관없고, 각 문자는 해당 회사의 새 빈 요청을 나타낸다. 어떤 변경 집합에도 빈이 항상 충분히 있다.

각 회사의 빈이 연속하도록 유지하면서 모든 빈 변경을 만족하는 데 필요한 최소 비용을 출력한다.