Inserting operators

You are given a sequence of $N$ numbers $A_1, A_2, \dots, A_N$, along with $N-1$ operators to insert between adjacent numbers. The operators are addition ($+$), subtraction ($-$), multiplication ($\times$), and division ($\div$) only.

Insert one operator between each pair of adjacent numbers to build an expression. The order of the given numbers must not change.

For example, if the sequence is 1, 2, 3, 4, 5, 6 and the operators are two additions, one subtraction, one multiplication, and one division, there are 60 possible expressions. Four of them are:

• $1+2+3-4\times5\div6$
• $1\div2+3+4-5\times6$
• $1+2\div3\times4-5+6$
• $1\div2\times3-4+5+6$

An expression is evaluated left to right, ignoring operator precedence. Division keeps only the quotient. When a negative number is divided by a positive number, divide the two absolute values and attach a minus sign to the quotient. Under these rules the four expressions above evaluate as follows:

• $1+2+3-4\times5\div6 = 1$
• $1\div2+3+4-5\times6 = 12$
• $1+2\div3\times4-5+6 = 5$
• $1\div2\times3-4+5+6 = 7$

Given $N$ numbers and $N-1$ operators, write a program that finds the maximum and the minimum result among the expressions you can build.

The first line contains the count of numbers $N$. ($2 \le N \le 11$)

The second line contains $A_1, A_2, \dots, A_N$ separated by spaces. ($1 \le A_i \le 100$)

The third line contains four integers whose sum is $N-1$. In order, they are the number of additions, the number of subtractions, the number of multiplications, and the number of divisions.

Print the maximum result on the first line and the minimum result on the second line.

Only inputs for which every placement of the operators yields a result of at least $-10^9$ and at most $10^9$ are given. Every intermediate result during the left to right evaluation is also at least $-10^9$ and at most $10^9$.

When the sequence is 1, 2, 3, 4, 5, 6 and the operators are two additions, one subtraction, one multiplication, and one division, the maximum and the minimum come from these expressions.

• Maximum: $1-2\div3+4+5\times6$
• Minimum: $1+2+3\div4-5\times6$