Willy Feels Guilty

지역사회 지원 농업(CSA)은 구독 과정을 통해 생산자와 소비자를 연결하는 훌륭한 식품 시스템 모델이다. Willy는 CSA 시스템을 오랫동안 지지해 온 사람이다. 회비를 낸 후, Willy는 때때로 지역 농부가 재배한 유기농 제품 하나가 담긴 새 바구니를 받게 된다는 것을 알고 있다.

이 시스템은 윤리적으로 훌륭하지만, 큰 단점이 하나 있다. 바로 Willy가 무엇을 받을지 결정하지 못한다는 점이다. Willy는 매우 편식하는 사람이기 때문에 이는 문제가 된다. 겨우내 지역산 양배추만 먹다 보면, 때로는 슈퍼마켓에서 직접 산 과즙이 풍부한 파인애플을 원할 수도 있다. 당근을 너무 많이 먹다 보면, 질려서 일부를 버릴 수도 있다. 때로는 친구와 채소를 교환하기로 결정할 수도 있다. 사실 Willy는 이미 자신의 정확한 식단을 정해 두었고, 이 특정한 순서의 제품만 (순서대로) 먹을 것이다. 그럼에도 Willy는 CSA 모델을 굳게 믿기 때문에, 구독에서 벗어날 때마다 죄책감을 느낀다.

당신의 임무는 Willy가 들어오는 배송을 관리하여 자신의 입맛과 정확히 일치시키면서 죄책감 비용을 최소화하도록 돕는 것이다. Willy가 CSA 계획에서 받게 될 제품 목록(그 순서대로)과 Willy가 먹을 제품의 식단(그 순서대로)이 주어진다. Willy는 세 가지 방식으로 구독에서 벗어날 수 있다. 제품을 버리거나, 슈퍼마켓에서 제품을 사거나, 한 제품을 다른 제품으로 교환하는 것이다. 또한 이러한 각 행동의 죄책감 비용(수행할 때마다 발생)도 주어진다. Willy가 자신의 식단에 따라 정확히 먹기 위해 지불해야 하는 최소 죄책감 비용은 얼마인가?

입력 파일은 여러 테스트 케이스로 구성된다. 입력 파일의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 하나가 있다. 각 테스트 케이스는 세 줄로 구성된다. 테스트 케이스의 첫 줄에는 세 정수 b, t, s가 단일 공백으로 구분되어 있다.

• 0 ≤ b ≤ 1000은 제품을 살 때의 죄책감 가격이다.
• 0 ≤ t ≤ 1000은 제품을 버릴 때의 죄책감 가격이다.
• 0 ≤ s ≤ 1000은 제품을 교환할 때의 죄책감 가격, 즉 Willy가 자신의 구독에 있는 특정 제품 하나를 친구에게 받은 다른 임의의 제품과 교환할 때의 가격이다.

테스트 케이스의 두 번째 줄은 Willy가 CSA 구독에서 받게 될 제품 목록을 나타낸다. 제품의 수를 나타내는 정수 1 ≤ n ≤ 1000으로 시작하고, 단일 공백과 n개의 제품 이름이 단일 공백으로 구분되어 이어진다. 각 제품 이름은 'a'에서 'z' 사이의 소문자 20자 이하의 비어 있지 않은 문자열이다. 테스트 케이스의 세 번째 줄은 Willy의 식단을 나타내며, 두 번째 줄과 같은 형식의 제품 목록이다. 같은 제품 이름이 같은 줄이나 여러 줄에 여러 번 나타날 수 있다. 제품 이름이 두 번째 줄에만 나타나거나 세 번째 줄에만 나타날 수도 있다.

입력의 각 테스트 케이스에 대해, 프로그램은 Willy가 자신의 식단에 있는 제품 순서대로 정확히 먹기 위해 겪어야 하는 최소 죄책감 비용을 나타내는 정수 하나를 한 줄에 출력해야 한다. 출력에 빈 줄이 있어서는 안 된다.