두 구역 데이터베이스

면접 대비

시간 제한1초메모리 제한256 MB

요약

주어진 순서대로 자료를 읽을 때 한 종류만 담는 무상 캐시를 복사 비용을 들여 활용해 총 읽기 비용을 최소화합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법
정답자: 아직 제출이 없습니다

문제

어떤 데이터베이스는 데이터를 두 구역에 나누어 둔다. 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에는 아무 데이터도 없다.

출력

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

예제6

예제 1
입력
```
1
10 3 5
2 2 4
1 1 1 1 1 2 2 2 3 2
```
예상 출력
```
14
```
예제 2
입력
```
1
1 1 0
1
1
```
예상 출력
```
0
```
예제 3
입력
```
1
6 2 1000
1 1
1 2 1 2 1 2
```
예상 출력
```
6
```
예제 4
입력
```
1
8 2 5
100 1
1 1 1 1 1 1 1 1
```
예상 출력
```
5
```

예제 5

입력

예상 출력

5
5
10

예제 6
입력
```
1
7 3 0
100 100 100
1 2 3 3 2 1 1
```
예상 출력
```
0
```