Unfair Division#1145
Albert and his two sisters, Betty and Karina, are dividing up their inherited property. The values of the items to be divided are written on a piece of paper in a list. Albert takes scissors and makes a cut between two numbers, dividing the list into two non-empty parts. Then Betty does the same to one of the parts, splitting it again, resulting in three parts. Next, Karina chooses the part with the maximum total value. From the remaining two parts, Betty makes her choice. The last remaining part goes to Albert.
Each participant aims to maximize their own inheritance. The sisters are upset with their brother and will choose in a way to punish him, as long as it doesn't reduce their own gain. For example, if one of the sisters has two different options resulting in the same total for herself, she will choose the option that gives her sister more (and Albert less).
Find the maximum value Albert can guarantee for himself with his first cut.
The first line contains the number of items (n \leq 50) to be divided. The second line contains integers — their values. Each item's value is between and .
Output the maximum value Albert can ensure for himself by making his first cut.
Example 1