### Problem Statement

You are given an int k and a int[] numbers containing exactly N elements. Choose exactly k distinct integers between 0 and N-1, inclusive, and arrange them in ascending order. The difference between each pair of consecutive elements in this sequence must be less than or equal to maxDist. Each element in this sequence represents a zero-based index into the int[] numbers. Multiply the corresponding elements of numbers together to obtain a product. Return the maximal possible product you can get.

### Definition

 Class: TheProduct Method: maxProduct Parameters: int[], int, int Returns: long Method signature: long maxProduct(int[] numbers, int k, int maxDist) (be sure your method is public)

### Constraints

-numbers will contain between 1 and 50 elements, inclusive.
-Each element of numbers will be between -50 and 50, inclusive.
-k will be between 1 and 10, inclusive.
-k will be less than or equal to the number of elements in numbers.
-maxDist will be between 1 and 50, inclusive.

### Examples

0)

 `{7, 4, 7}` `2` `1`
`Returns: 28`
 The maximal distance is 1, so we can't choose both 7's.
1)

 `{7, 4, 7}` `2` `50`
`Returns: 49`
 And now it's possible.
2)

 `{-3, -5, -8, -9, -1, -2}` `3` `3`
`Returns: -10`
 Here, the product will always be negative, so we need to find the product with the smallest absolute value.
3)

 `{3, 0, -2, 10, 0, 0, 3, -8, 0, 2}` `2` `2`
`Returns: 0`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14174&pm=10421

Vasyl[alphacom]

#### Testers:

PabloGilberto , ivan_metelsky , Xixas

#### Problem categories:

Greedy, Simple Math, Sorting