### Problem Statement

There are 3*N pie pieces arranged in a circle. You and Ted are going to eat the whole pie using the following rules. You can choose any piece and eat it, but Ted will eat its left and right neighbors (once a piece is eaten its left and right neighbors become neighbors themselves). This operation is repeated until the whole pie is eaten (in other words N times). You are planning to eat as big a part of the pie as possible.

You will be given int[] pieces. pieces[i] is the size of the i-th piece as a percentage (between 1 and 100). Return the maximum percentage of the pie that you can eat.

### Definition

 Class: PieSharing Method: share Parameters: int[] Returns: int Method signature: int share(int[] pieces) (be sure your method is public)

### Constraints

-pieces will have between 3 and 48 elements, inclusive.
-The number of elements in pieces will be divisible by 3.
-Each element in pieces will be between 1 and 100, inclusive.
-The elements in pieces will sum up to 100.

### Examples

0)

 {33, 33, 34}
Returns: 34
 You can eat the biggest piece.
1)

 {5, 17, 22, 34, 18, 4}
Returns: 51
 You can eat pieces with sizes 34 and 17.
2)

 {11, 1, 1, 85, 1, 1}
Returns: 96
 You will eat almost the whole pie.
3)

 {6, 13, 14, 4, 14, 10, 1, 20, 18}
Returns: 48

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8002&pm=4620

Andrew_Lazarev

#### Testers:

PabloGilberto , brett1479 , Olexiy

#### Problem categories:

Dynamic Programming