The Agency

당신은 행성 간 여행 서비스를 만들고 있으며, 첫 번째 과제는 두 행성 사이를 가장 저렴하게 이동하는 방법을 찾는 것입니다. 다행히 행성들과 그 사이의 항로에는 특별한 구조가 있습니다. 각 행성은 N개의 비트로 이루어진 문자열로 표현됩니다. 두 행성의 N비트 문자열이 정확히 한 자리에서만 다를 때(즉 비트 하나만 뒤집혔을 때), 그 두 행성 사이에는 직항편이 있습니다.

한 항로의 비용은 도착 행성에 착륙하는 비용입니다. 각 비트 위치 i에는 대응하는 세금이 있습니다. 어떤 행성에 착륙하려면, 그 행성 문자열에서 비트가 1인 모든 위치 i에 대해 i번째 세금을 내야 하므로, 한 행성에 착륙하는 비용은 이러한 해당 세금들의 합입니다. 출발 행성에 있는 것 자체에는 비용이 들지 않으며, 이동해 착륙하는 각 행성에 대해서만 비용을 냅니다.

출발 행성, 도착 행성, 그리고 각 세금의 비용이 주어질 때, 출발 행성에서 도착 행성까지 가는 항로들의 최소 총비용을 구하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 두 줄로 구성됩니다. 첫째 줄에는 행성을 나타내는 비트 수 N (1 ≤ N ≤ 1000), 출발 행성을 나타내는 0과 1로 이루어진 길이 N의 문자열 S, 도착 행성을 나타내는 같은 형식의 문자열 E가 주어집니다. 둘째 줄에는 N개의 정수가 있으며, i번째 값은 i번째 세금의 비용입니다(비트 위치는 1부터 번호가 매겨집니다). 모든 세금은 1 이상 1,000,000 이하입니다. 0 하나만 있는 줄이 입력의 끝을 나타냅니다.

각 테스트 케이스마다 한 줄에 Case k: c를 출력합니다. 여기서 k는 테스트 케이스 번호(1부터 시작)이고, c는 출발 행성에서 도착 행성까지 이동하는 최소 총비용입니다.