Find Minimum Cost to Shift Machines

Each region has a positive number of machines. Adding or removing one machine costs 1, but a region cannot be reduced to 0; migrating all machines of one region into another region costs c, and the source region disappears. In the end, it is only required that three regions have machine counts matching the three targets one-to-one; other regions may remain. Find the minimum cost. The output 2 in original example 2 is a typo; both its steps and the complete supplementary source give 5.

输入格式

The input is n, n initial counts, 3 target counts, and the migration cost c. The complete original bounds from the main raw are kept: 3≤n≤10, and initial and target counts in 1..10^6. The original gave no range for c; this site adds 0≤c≤10^6. The auxiliary raw only corroborates example 5, and its different bound on n is not mixed into this problem.

输出格式

Output a single integer, the answer.

样例 1

输入：

4
2 4 5 3
4 4 4
5

输出：

2

样例 2

输入：

4
2 3 5 7
5 10 5
2

输出：

5

样例 3

输入：

3
1 1 1
1 1 1
0

输出：

0

样例说明

The outputs of the three public examples are, in order: 2; 5; 0. Verified by independent enumeration or direct simulation.