시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB41322514451.986%

문제

$N$개의 양의 정수 $X_{i}$와 곱하기 연산자, 더하기 연산자가 총 $N - 1$개가 존재하고 괄호는 무수히 많이 사용해도 된다. 이 연산에는 곱하기 연산자와 더하기 연산자의 우선순위가 동일하다.

정수와 연산자는 아래와 같이 배치해야한다. 정수의 순서는 바꿔도 상관없다.

예를 들어 정수 $1$, $2$, $3$이 있고 더하기 연산자와 곱하기 연산자가 각각 하나 있다고 가정하면 아래와 같이 만들 수 있다. 

예를 들어, 수 $1, 2, 4, 5, 7, 8$와 더하기 연산자가 4개 곱하기 연산자가 1개 있다고 하자. 괄호를 이용하여 최대값을 구하는 방법 중 일부이다.

  • $(((1+2)+4)+7) × (5+8)$
  • $((1+2)+(4+7)) × (5+8)$
  • $(1+(2+4)+7) × (5+8)$
  • $(1+2+4+7) × (5+8)$

연산을 잘 이용하여 값을 최대로 만들어 보자.

입력

첫째 줄에 입력될 양의 정수 개수를 뜻하는 $N$이 주어진다.

그 다음줄에는 $N$개의 양의 정수 $X_{i}$가 공백으로 구분되어 주어진다.

마지막 줄에는 더하기 연산자의 개수 $P$와 곱하기 연산자의 개수 $Q$가 공백으로 구분되어 주어진다.

출력

가능한 연산의 결과 중 최댓값을 출력한다.

제한

  • $1 \le N \le 8$
  • $1 \le X_{i} \le 9$
  • $0 \le P, Q \le N - 1$
  • $P + Q = N - 1$

예제 입력 1

6
1 2 4 5 7 8
4 1

예제 출력 1

182

예제 입력 2

3
1 9 1
2 0

예제 출력 2

11

예제 입력 3

5
1 2 3 4 5
1 3

예제 출력 3

180

출처