### Problem Statement

There are several sumo wrestlers registered for the current season. You are given a int[] weight, where the i-th element is the weight of the i-th wrestler. One or more of these wrestlers are registered in this week's tournament. You are given an int averageWeight, which is the exact average weight of the wrestlers registered in the tournament. Return the maximal possible weight of a wrestler who might be in this tournament, or -1 if the average is not possible with the given input.

### Definition

 Class: SumoTournament Method: maxWeight Parameters: int[], int Returns: int Method signature: int maxWeight(int[] weight, int averageWeight) (be sure your method is public)

### Constraints

-averageWeight will be between 1 and 200, inclusive.
-weight will contain between 1 and 50 elements, inclusive.
-Each element of weight will be between 1 and 200, inclusive.

### Examples

0)

 `{80,90,100}` `90`
`Returns: 100`
 There are three possible tournaments with an average weight of 90: {80,90,100}, {80,100}, {90}. Thus, it is possible that the wrestler with weight 100 is in the tournament.
1)

 `{81,90,150}` `90`
`Returns: 90`
2)

 `{10,20}` `15`
`Returns: 20`
3)

 `{40,30,20,10}` `27`
`Returns: -1`
 There is no way to achieve an average weight of 27.

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10776&pm=7660

Janq

#### Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

#### Problem categories:

Dynamic Programming, Simple Math, Simple Search, Iteration