### Problem Statement

You've collected data in a int[] dogs which describes how many dogs are present in each neighborhood of your city, and you wish to represent this data in a pie chart. The total number of dogs in your city is exactly 100, so if a neighborhood has 15 dogs, it will form a solid region in the chart with an area equal to 15% of the whole pie chart.

Given a pie chart, a dividing line is a line that passes through the center of the chart and doesn't pass through the interior of any solid region of the chart. For example, the chart on the left has two dividing lines, while the chart on the right has only one dividing line (see examples 0 and 1 for the data that forms these two charts). Note that there may be several ways to create a pie chart from the same data. Return the maximum number of dividing lines in a pie chart that can be made from the data.

### Definition

 Class: SymmetricPie Method: getLines Parameters: int[] Returns: int Method signature: int getLines(int[] dogs) (be sure your method is public)

### Constraints

-dogs will contain between 1 and 8 elements, inclusive.
-Each element of dogs will be between 1 and 100, inclusive.
-The sum of all elements of dogs will be exactly 100.

### Examples

0)

 `{10,40,10,40}`
`Returns: 2`
 This is the left pie chart in the problem statement's diagram.
1)

 `{10,50,40}`
`Returns: 1`
 This is the right pie chart in the problem statement's diagram.
2)

 `{50,50}`
`Returns: 1`
 The only line here divides the chart through the center.
3)

 `{1,48,1,1,48,1}`
`Returns: 3`
 The best solution here is to put the regions in the order (1,1,48,1,1,48), giving us 3 dividing lines.
4)

 `{2,2,96}`
`Returns: 0`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12178&pm=8784

eleusive

#### Testers:

PabloGilberto , Olexiy , gawry , ivan_metelsky

Brute Force