Two-Area Database

Interview

Time limit1sMemory limit256 MB

Summary

Read a fixed sequence of data kinds using a one-slot cache that loads at cost c and serves hits for free, and minimize total read cost.

Level: Medium5 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

A database keeps its data in two areas. Area0 holds every kind of data. Area1 holds exactly one kind at a time.

Reading the $i$ -th kind of data from Area0 costs $c_i$ . Reading the data currently held in Area1 costs nothing.

You may pick any one kind of data in Area0 and copy it into Area1. The copy costs $c$ whichever kind you pick, and it erases whatever Area1 held before. You may copy at any moment and as many times as you want, and a copy leaves Area0 unchanged.

The kinds of data to read today and their order are fixed in advance and are all given to you. Area1 starts empty.

Find the smallest total cost of reading all of the data in the given order.

Input

The first line contains the number of test cases $T$ .

The first line of each test case contains three integers separated by spaces: the number of reads to perform today $n$ ( $1 \le n \le 100\,000$ ), the number of kinds of data $m$ ( $1 \le m \le 30$ ), and the cost $c$ ( $0 \le c \le 1\,000$ ) of copying one piece of data from Area0 into Area1.

The second line contains $m$ integers $c_1, c_2, \dots, c_m$ ( $1 \le c_i \le 100$ ) separated by spaces. $c_i$ is the cost of reading the $i$ -th kind of data from Area0.

The third line contains $n$ integers $d_1, d_2, \dots, d_n$ ( $1 \le d_i \le m$ ) separated by spaces. $d_i$ is the kind of data that must be read $i$ -th.

At the start every kind of data is stored in Area0 and Area1 is empty.

Output

For each test case, print the minimum cost of reading all of the data in order, one answer per line.

Examples6

Example 1
Input
```
1
10 3 5
2 2 4
1 1 1 1 1 2 2 2 3 2
```
Expected output
```
14
```
Example 2
Input
```
1
1 1 0
1
1
```
Expected output
```
0
```
Example 3
Input
```
1
6 2 1000
1 1
1 2 1 2 1 2
```
Expected output
```
6
```
Example 4
Input
```
1
8 2 5
100 1
1 1 1 1 1 1 1 1
```
Expected output
```
5
```

Example 5

Input

Expected output

5
5
10

Example 6
Input
```
1
7 3 0
100 100 100
1 2 3 3 2 1 1
```
Expected output
```
0
```