Background

You find yourself playing the role of a kind lady working as a cashier in the cafeteria. One of the many reasons all students think she is a good person is that she cares about making you spend as little money as possible when you visit the cafeteria.

Problem Description

How does she do this? The strategy is actually very simple. In the cafeteria, you can buy various dishes, and their prices are well known. Every day, there is a set meal. A set meal includes $4$ dishes (usually soup, main course, side dish, and dessert), but its price $x$ is less than or equal to the sum of the prices of its components. The lady has noticed that if you take some individual items that are part of the set meal, and if paying for a whole set meal would cost less, then she will definitely do so, and you will leave with a full tray and more money left in your pocket than before.

You are standing at the cashier with your tray, wondering how much you need to pay. Write a program to determine it.

Note: The lady may charge you using multiple set meals if that makes the total price cheaper.

Input Format

The input consists of six lines.

The first line contains an integer $k$, the total number of dishes available in the cafeteria today.
The second line contains $k$ integers; the $i$-th integer $c_i$ is the price of the $i$-th dish.
The third line contains an integer $x$, the price of the set meal.
The fourth line contains $4$ integers $p_1,p_2,p_3,p_4$, representing the $4$ dishes included in the set meal. It is guaranteed that the $p_i$ are pairwise distinct.
The fifth line contains an integer $t$, the number of dishes you ordered.
The sixth line contains $t$ integers; the $i$-th integer $s_i$ is the index of the $i$-th dish you ordered. The $s_i$ are not guaranteed to be pairwise distinct.

Output Format

Output a single line containing one integer, the amount of money you spend in the cafeteria today.

7
10 6 8 9 4 5 3
14
1 2 3 4
5
1 3 4 6 7

22

6
12 5 7 8 9 3
14
4 3 1 2
5
1 2 1 6 6

32

Hint

[Sample 1 Explanation]

You ordered dishes $1,3,4$, which are in the set meal. The total price if bought separately is $10+8+9=27$, which is greater than the set meal price $14$, so the cashier lady will charge these dishes as $14$. The other two dishes $6,7$ are not in the set meal, so they are charged separately. Therefore, the total cost is $14+5+3=22$.

[Sample 2 Explanation]

You ordered dishes $1,2$, which are in the set meal. The total price if bought separately is $12+4=16$, which is greater than the set meal price $14$, so the cashier lady will charge these dishes as $14$. In addition, there is one more dish $1$ and two dishes $6$ left. Since the price of one dish $1$ is $12$, which is less than the set meal price $14$, and the two dishes $6$ do not appear in the set meal, the remaining one dish $1$ and the two dishes $6$ can only be charged separately. Therefore, the total cost is $14+12+3\times 2=32$.

[Constraints]

For all testdata, $1\leqslant k,t\leqslant 20$, $1\leqslant c_i\leqslant 250$, $1\leqslant x<1000$, $1\leqslant p_i,s_i\leqslant k$.

[Source]

This problem comes from COCI 2014-2015 CONTEST 7 T1 TETA, and uses the original testdata configuration, with a full score of $50$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5