10719번 - Baekjoon Database Management System

백준 온라인 저지에서는 예언자 백준이 개발한 BDBMS(Baekjoon DataBase Management System)을 사용한다.

혁신을 좋아하는 백준은 BDBMS 역시 혁신적인 디자인으로 설계하였다.

BDBMS는 일반적인 데이터를 저장하는 Area0 외에, 단 하나의 데이터만을 저장할 수 있는 Area1을 제공하며, 이 Area는 정말 혁신적인 기능을 탑재하고 있었다: 비록 동시에 한 종류의 데이터만 기억할 수 있지만, 혁신적인 개량을 통해서 개발된 Area1은 자신에게 저장된 데이터를 읽을 때 비용이 들지 않는다!

또한 백준은 예언자이기 때문에 매일 아침 신탁을 통해서 오늘 접근될 데이터의 순서를 미리 알 수가 있다.

백준은 데이터의 순서와 BDBMS의 기능을 이용하여 오늘 이루어질 데이터 접근을 가장 효율적으로 진행해 최소 비용으로 해결하고 싶어한다.

사탕보다 프로그래밍을 좋아하는 당신이라면 분명 백준이 원하는 해답을 찾아 줄 수 있을 것이다.

백준을 도와 가장 효율적인 BDBMS 운용법을 찾아내자!

첫 줄에는 테스트 케이스의 숫자 \(T\)가 정수로 주어진다.

이어서 각 테스트 케이스별로 첫 줄에는 오늘 수행해야 할 데이터 접근 횟수 \(n(1 \leq n \leq 100,000)\)과 데이터의 종류 \(m(1 \leq m \leq 30)\), 그리고 임의의 Area0에 있는 데이터를 Area1로 복사하는데 드는 비용 \(c(0 \leq c \leq 1,000)\)이 공백으로 구분되어 정수로 주어진다.

다음 줄에는 \(m\) 개의 정수 \(c_i (1 \leq c_i \leq 100, 1 \leq i \leq m)\)가 공백으로 구분되어 주어지며, 각 정수는 Area0에 있는 \(i\)번째 데이터를 읽을 때 드는 비용이다.

다음 줄에는 \(n\) 개의 정수 \(d_i (1 \leq d_i \leq m, 1 \leq i \leq n)\)가 공백으로 구분되어 주어지며, \(d_i\)는 \(i\)번째로 읽어져야 할 데이터의 종류를 뜻한다.

제일 처음에 모든 데이터는 Area0에 저장되어 있으며 Area1에는 아무런 데이터도 들어있지 않다.

각 테스트 케이스마다 한 줄에 걸쳐 모든 데이터를 읽는 데 걸리는 최소 비용을 출력한다.