Inserting Operators (3)

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

Put one operator into each gap between two neighboring numbers to build a single expression. The order of the given numbers must not change.

For example, if the sequence is 1, 2, 3, 4, 5, 6 and the given operators are two additions, one subtraction, one multiplication and one division, there are 60 expressions in total. 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 by operator precedence. $\times$ and $\div$ come before $+$ and $-$, and operators of equal precedence are applied from left to right. Division is integer division that keeps only the quotient. Under these rules the four expressions above evaluate to:

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

Given $N$ numbers and $N-1$ operators, write a program that finds the largest and the smallest value an expression can take.

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$ ($1 \le A_i \le 100$). The third line contains four integers whose sum is $N-1$: the number of additions, subtractions, multiplications and divisions, in that order.

Print the largest value an expression can take on the first line, and the smallest value on the second line. Only inputs whose largest and smallest values are at least -1,000,000,000 and at most 1,000,000,000 are given. Every value computed along the way is also at least -1,000,000,000 and at most 1,000,000,000, in whatever order the expression is evaluated.

For the input where the sequence is 1, 2, 3, 4, 5, 6 and the operators are two additions, one subtraction, one multiplication and one division, these two expressions give the largest and the smallest value.

• Largest: $1-2\div3+4+5\times6$
• Smallest: $1+2+3\div4-5\times6$