### Problem Statement

There is a shop in your city, in which matches of different integer thicknesses from 1 to N, inclusive, are sold. All matches in the shop have the same length. The (i-1)-th element of cost is the cost of one match with thickness i.

You wish to buy some matches and use them to construct a 2xM rectangle. For example, if M=5, then the rectangle will look as follows (characters '|' and '-' correspond to matches):

``` _ _ _ _ _
| | | | | |
_ _ _ _ _
| | | | | |
_ _ _ _ _
```

You are given two int[]s, top and bottom, each containing exactly M elements. top and bottom contain the required thicknesses of the squares in the top and bottom rows of the rectangle, respectively, from left to right. The thickness of a square is the sum of the thicknesses of its four sides. Return the minimum total cost of matches needed to construct the required rectangle, or -1 if it's not possible.

### Definition

 Class: ConstructionFromMatches Method: minimumCost Parameters: int[], int[], int[] Returns: int Method signature: int minimumCost(int[] cost, int[] top, int[] bottom) (be sure your method is public)

### Constraints

-cost will contain between 1 and 12 elements, inclusive.
-Each element of cost will be between 1 and 100000, inclusive.
-Elements of cost will be in strictly ascending order.
-top will contain between 1 and 50 elements, inclusive.
-bottom will contain the same number of elements as top.
-Each element of top and bottom will be between 4 and 48, inclusive.

### Examples

0)

 `{1, 2}` `{7}` `{5}`
`Returns: 10`
 The cheapest solution contains 3 matches of thickness 2 and 4 matches of thickness 1. It may look as follows (each digit d denotes a single match of thickness d): ``` 1 2 2 2 1 1 1 ```
1)

 `{1}` `{5}` `{5}`
`Returns: -1`
 Obviously we can't get a square with thickness 5 using only matches of thickness 1.
2)

 `{1, 5, 9}` `{7, 10}` `{8, 9}`
`Returns: 56`
 One of the optimal solutions looks as follows (each digit d denotes a single match of thickness d): ``` 1 3 1 3 1 2 3 1 3 1 2 2 ```
3)

 `{1, 3, 4, 7, 9}` `{13, 14, 13, 11, 9, 7, 11, 8, 8, 10}` `{18, 14, 17, 10, 8, 4, 8, 13, 14, 13}`
`Returns: 194`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8146

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10888&pm=8146

ivan_metelsky

#### Testers:

PabloGilberto , vorthys , Olexiy

#### Problem categories:

Dynamic Programming