Maximize the Expression

Interview

Time limit1sMemory limit512 MB

Summary

Arrange N given positive integers with P addition and Q multiplication operators, in any order and with any parentheses, to maximize the result.

Level: Medium5 of 10
Topics: Brute force, Backtracking, Greedy, Combinatorics
Solved: No attempts yet

Problem

There are $N$ positive integers $X_{i}$ and a total of $N - 1$ operators, each either a multiplication operator or an addition operator. You may use as many parentheses as you like. In this expression, the multiplication operator and the addition operator have the same precedence.

Integers and operators must be arranged as shown below. The order of the integers may be changed.

For example, suppose there are the integers $1$ , $2$ , $3$ and one addition operator and one multiplication operator. Then an expression like the one below can be made.

For example, suppose there are the numbers $1, 2, 4, 5, 7, 8$ , four addition operators, and one multiplication operator. Some of the ways to obtain the maximum value using parentheses are:

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

Use the operations well to make the value as large as possible.

Input

The first line gives $N$ , the number of positive integers to be used.

The next line gives the $N$ positive integers $X_{i}$ , separated by spaces.

The last line gives the number of addition operators $P$ and the number of multiplication operators $Q$ , separated by a space.

Output

Print the maximum value among all possible results of the operations.

Constraints

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

Examples3

Example 1
Input
```
6
1 2 4 5 7 8
4 1
```
Expected output
```
182
```
Example 2
Input
```
3
1 9 1
2 0
```
Expected output
```
11
```
Example 3
Input
```
5
1 2 3 4 5
1 3
```
Expected output
```
180
```