H. Eating Pie
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Joaozao and Nicoleta are planning to buy some pies at the local market. There are K different types of pies and Joaozao only buys pies of the types that are on his list of preferred pie types. The same goes for Nicoleta, who only buys pies of the types that are on his list of preferred pie types. It's guaranteed that every type of pie appears on at least one list of preferences.

The local market is doing a special pie sale. Because of this, all N pies are lined up in a row. The first pie in the row is of type p1, the second pie is of type p2 and so on until the N-th pie that is of type pN. It is guaranteed that the market sells all types of pies (i.e. each one of the K types of pies will appear at least once in this row). The special promotion of this sale was: if the same person buys pie i and pie i + 1, where i is the position of the pie in the row, this person gets gi candies.

Pies of the same type cannot be bought by different people (i.e. if Joaozao buys one pie of type t, then he has to buy all other pies of the same type t).

Joaozao and Nicoleta decided they will buy all N pies in the row and they want to maximize the total amount of candies they will earn. Given the lists of preferences for each one of them, the type of the pies in the row and the amount of candies that is earned for each pair of consecutive pies, can you tell what is the maximum total amount of candies they can get?

The total amount of candies is the sum of the candies earned by each of them.

Input

The first line of the input contains four integers K (2 ≤ K ≤ 500), N (K ≤ N ≤ 103), A and B (1 ≤ A, B ≤ K) indicating, respectively, the number of types of pies, the number of pies in the row of pies, the size of Joaozao's preference list and the size of Nicoleta's preference list. Pie types are numbered from 1 to K.

The second line contains A integers, the types of pies that Joaozao prefers.

The third line contains B integers, the types of pies that Nicoleta prefers.

It's guaranteed that all the different types of pies will appear in at least one list of preferences.

The fourth line contains N integers. The i-th integer of this line indicates the type of the i-th pie of the row, as described in the statement. Each of the K types of pie will appear at least once.

The fifth and last line contains N - 1 integers. The i-th integer of this line gi (1 ≤ gi ≤ 103) corresponds to the amount of candies earned when buying the i-th and the (i + 1)-th pie.

Output

Output a single integer indicating the maximum total amount of candies that Joaozao and Nicoleta can earn.

Examples
Input
4 6 1 3
1
2 3 4
1 3 2 2 4 1
1 2 4 8 16
Output
14
Input
4 10 3 3
1 2 3
2 3 4
1 2 3 4 3 1 2 4 3 1
1 1 5 5 2 2 1 5 1
Output
18
Note

In the first case, to maximize the total amount of candies earned, Joaozao should buy the pies in positions 1 and 6 (1-indexed). Nicoleta should buy the rest.

In the second case, the pies that Joaozao should buy are in positions 1, 2, 6, 7 and 10. Nicoleta should buy the pies in positions 3, 4, 5, 8, 9.