Given a sequence $w_{1}, w_{2}, \dots, w_{n}$ of length $n$, there is a sequence $a_{1}, a_{2}, \dots, a_{m}$ of length $m$, initially $a_{i}=0$ for all $1 \le i \le m$.
There are $q$ requests, each containing a number $k$:
- If there exists $1 \le i \le m$ such that $a_{i}=k$, no operation is performed.
- Otherwise, pay a cost of $w_{k}$, and choose an index $1 \le i \le m$ to update $a_{i}=k$.
Find the minimum total cost.
Input
The first line contains three integers $n, m, q$. The second line contains $n$ integers $w_{1}, w_{2}, \dots, w_{n}$. The third line contains $q$ integers $k_{1}, k_{2}, \dots, k_{q}$.
Output
A single integer representing the answer.
Examples
Input 1
3 2 5 1 2 3 1 2 3 2 1
Output 1
7
Note
For the first operation, set $a_{1}=1$. For the second operation, set $a_{2}=2$. For the third operation, set $a_{1}=3$. For the fourth operation, no change is made. For the fifth operation, set $a_{1}=1$. The total cost is $1+2+3+0+1=7$.
Constraints
$1 \le n, q \le 5 \times 10^{3}$, $1 \le m \le 15$, $1 \le w_{i} \le 10^{5}$ for all $1 \le i \le n$, $1 \le k_{i} \le n$ for all $1 \le i \le q$.
Subtasks
- Subtask 1 (20 points): $1 \le n \le 10$
- Subtask 2 (20 points): $m=2$
- Subtask 3 (20 points): $n=5 \times 10^{3}$, $m=15$, $q=400$, and $k_{i}$ are uniformly random in $[1, n]$
- Subtask 4 (20 points): $1 \le q \le 10^{3}$
- Subtask 5 (20 points): No additional constraints