For years, Albert has picked on his sisters Betty and Carla, and now he is about to pay the price. The siblings' parents - firm believers in the "I cut, you choose" method of division - have died and have left instructions in their will about how their assets are to be divided. The assets have been written down in a single long list. Albert has been given scissors and must carefully cut between two entries to divide the list into two non-empty sublists. Betty will then be given the scissors and will do the same to one of the sublists, leaving a total of three sublists. Carla will then choose one of the sublists and will receive all the assests in that sublist. Next, Betty will choose between the two remaining sublists and will receive those assets. Finally, Albert will receive the assets on the last remaining sublist.

Naturally, each person wants to maximize their own share, but, because of certain regrettable childhood incidents, Betty and Carla will each try to punish Albert, as long as they can do so at no cost to themselves. For example, if Betty has two options that will both net her $1000, then she will always choose the option that will give Carla more money and Albert less money. On the other hand, if Betty has two options that will give her different amounts of money, then she will always choose the option that will give herself the most money.

As Albert raises the scissors to make the first cut, he wonders how much he is going to end up with. Given a list, representing the values of the assets in the list, in the same order as the list, calculate the total value of Albert's share, assuming that all parties have full knowledge of each other's strategies and make their decisions optimally.

Input

The first line contains the number of assets n (n ≤ 50) to be divided. The next line contains n integers - the prices of the assets. All prices are integers between 1 and 1000.

Output

Print the maximum possible value of Albert's share that he can obtain with his first cut.