연산자 끼워넣기 (3)

$N$개의 수로 이루어진 수열 $A_1, A_2, \dots, A_N$이 주어진다. 수와 수 사이에 끼워넣을 $N-1$개의 연산자도 함께 주어지고, 연산자는 덧셈($+$), 뺄셈($-$), 곱셈($\times$), 나눗셈($\div$) 네 가지뿐이다.

수와 수 사이에 연산자를 하나씩 넣어 수식 하나를 만든다. 이때 주어진 수의 순서는 바꾸지 못한다.

예를 들어 수열이 1, 2, 3, 4, 5, 6이고 주어진 연산자가 덧셈 2개, 뺄셈 1개, 곱셈 1개, 나눗셈 1개이면 만들 수 있는 식은 모두 60가지다. 그중 네 가지는 다음과 같다.

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

식은 연산자 우선순위에 따라 계산한다. $\times$와 $\div$가 $+$와 $-$보다 앞서고, 우선순위가 같으면 앞에 있는 연산부터 계산한다. 나눗셈은 몫만 취하는 정수 나눗셈이다. 이 규칙으로 위 네 식을 계산하면 값은 다음과 같다.

• $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$

$N$개의 수와 $N-1$개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

첫째 줄에 수의 개수 $N$($2 \le N \le 11$)이 주어진다. 둘째 줄에 $A_1, A_2, \dots, A_N$이 주어진다($1 \le A_i \le 100$). 셋째 줄에는 합이 $N-1$인 정수 네 개가 주어진다. 차례대로 덧셈, 뺄셈, 곱셈, 나눗셈의 개수다.

첫째 줄에 만들 수 있는 식의 결과 중 최댓값을, 둘째 줄에 최솟값을 출력한다. 최댓값과 최솟값이 항상 -10억 이상 10억 이하인 입력만 주어진다. 또 식을 어떤 순서로 계산해도 중간에 계산되는 식의 결과가 항상 -10억 이상 10억 이하다.

수열이 1, 2, 3, 4, 5, 6이고 연산자가 덧셈 2개, 뺄셈 1개, 곱셈 1개, 나눗셈 1개인 입력에서는 다음 두 식이 각각 최댓값과 최솟값을 만든다.

• 최댓값: $1-2\div3+4+5\times6$
• 최솟값: $1+2+3\div4-5\times6$