두 구역 데이터베이스

어떤 데이터베이스는 데이터를 두 구역에 나누어 둔다. Area0은 모든 종류의 데이터를 담고 있고, Area1은 한 번에 한 종류만 담는다.

Area0에 있는 $i$번째 종류의 데이터를 읽으면 비용 $c_i$가 든다. Area1에 들어 있는 데이터를 읽는 비용은 0이다.

Area0에 있는 데이터 중 하나를 골라 Area1로 복사할 수 있다. 복사 비용은 종류와 관계없이 $c$이고, Area1에 있던 이전 데이터는 지워진다. 복사는 원하는 시점에 원하는 횟수만큼 할 수 있으며, 복사해도 Area0의 데이터는 그대로 남는다.

오늘 읽어야 할 데이터의 종류와 그 순서는 미리 정해져 있고 전부 주어진다. 처음에 Area1은 비어 있다.

주어진 순서대로 데이터를 모두 읽을 때 드는 비용의 최솟값을 구하여라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 오늘 수행할 데이터 접근 횟수 $n$ ($1 \le n \le 100\,000$), 데이터의 종류 수 $m$ ($1 \le m \le 30$), Area0의 데이터 하나를 Area1로 복사하는 비용 $c$ ($0 \le c \le 1\,000$)가 공백으로 구분되어 정수로 주어진다.

둘째 줄에는 정수 $m$개 $c_1, c_2, \dots, c_m$ ($1 \le c_i \le 100$)이 공백으로 구분되어 주어진다. $c_i$는 Area0에 있는 $i$번째 종류의 데이터를 읽는 비용이다.

셋째 줄에는 정수 $n$개 $d_1, d_2, \dots, d_n$ ($1 \le d_i \le m$)이 공백으로 구분되어 주어진다. $d_i$는 $i$번째로 읽어야 할 데이터의 종류다.

처음에 모든 데이터는 Area0에 저장되어 있고, Area1에는 아무 데이터도 없다.

각 테스트 케이스마다 모든 데이터를 순서대로 읽는 데 필요한 최소 비용을 한 줄에 하나씩 출력한다.