404347: GYM101484 H Eating Pie

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 p₁, the second pie is of type p₂ and so on until the N-th pie that is of type p_N. 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 g_i 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.

The first line of the input contains four integers K (2 ≤ K ≤ 500), N (K ≤ N ≤ 10³), 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 g_i (1 ≤ g_i ≤ 10³) corresponds to the amount of candies earned when buying the i-th and the (i + 1)-th pie.

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

4 6 1 3
1
2 3 4
1 3 2 2 4 1
1 2 4 8 16

14

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

18

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.