### Problem Statement

Johnny has some number of rectangular bricks. He can put bricks on top of each other to build a tower. He wishes to build two towers of equal height out of his bricks (each tower must contain at least one brick). He also wants the towers to be as tall as possible. Note that Johnny doesn't have to use all the bricks.

You are given a int[] bricks, where each element is the height of a single brick. Return the height of the tallest towers of equal height that Johnny can build. If it's impossible to build two towers of equal height, return -1 instead.

### Definition

 Class: EqualTowers Method: height Parameters: int[] Returns: int Method signature: int height(int[] bricks) (be sure your method is public)

### Constraints

-bricks will contain between 1 and 50 elements, inclusive.
-Each element of bricks will be between 1 and 500000, inclusive.
-The sum of all elements of bricks will not be greater than 500000.

### Examples

0)

 `{ 2, 3, 5 }`
`Returns: 5`
 Johnny can build two towers of height 5. One contains a single brick of height 5, and the other contains a brick of height 2 and a brick of height 3.
1)

 `{ 10, 9, 2 }`
`Returns: -1`
 There's nothing Johnny can do here.
2)

 `{ 11, 11 }`
`Returns: 11`
3)

 `{ 14, 3, 20, 15, 15, 14, 24, 23, 15 }`
`Returns: 64`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13750&pm=10466

mateuszek

#### Testers:

PabloGilberto , kalinov , ivan_metelsky

#### Problem categories:

Dynamic Programming