연산자 끼워넣기

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

식은 연산자 우선순위를 무시하고 앞에서부터 차례로 계산한다. 나눗셈은 몫만 취한다. 음수를 양수로 나눌 때는 두 수의 절댓값끼리 나눈 몫에 음수 부호를 붙인다. 이 규칙으로 위 네 식을 계산한 결과는 다음과 같다.

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

$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^9$ 이상 $10^9$ 이하인 입력만 주어진다. 앞에서부터 계산하는 도중의 중간 결과도 항상 $-10^9$ 이상 $10^9$ 이하다.

수열이 1, 2, 3, 4, 5, 6이고 연산자가 덧셈 2개, 뺄셈 1개, 곱셈 1개, 나눗셈 1개인 경우, 최댓값과 최솟값은 다음 식에서 나온다.

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