Alphonse has \(N\) rice balls of
various sizes in a row. He wants to form the largest rice ball possible
for his friend to eat. Alphonse can perform the following
operations:

• If two adjacent rice balls have the same size,
  Alphonse can combine them to make a new rice ball. The new rice ball’s
  size is the sum of the two old rice balls’ sizes. It occupies the
  position in the row previously occupied by the two old rice
  balls.

• If two rice balls have the same size, and there is
  exactly one rice ball between them,
  Alphonse can combine all three rice balls to make a new rice ball. (The
  middle rice ball does not need to have the same size as the other two.)
  The new rice ball’s size is the sum of the three old rice balls’ sizes.
  It occupies the position in the row previously occupied by the three old
  rice balls.

Alphonse can perform each operation as many times as he wants.

Determine the size of the largest rice ball in the row after
performing 0 or more operations.

\((1 \leq N \leq 400)\)
\(N \leq 10\)
\(N \leq 50\)

The first line will contain the integer, \(N\) \((1 \leq N \leq 400)\).

The next line will contain \(N\)
space separated integers representing the sizes of the riceballs, in
order from left to right. Each integer is at least \(1\) and at most \(1\ 000\ 000\).

• For 1 of the 15 available marks, \(N = 4\).

• For an additional 2 of the 15 available marks, \(N \leq 10\).

• For an additional 5 of the 15 available marks, \(N \leq 50\).

Output the size of the largest riceball Alphonse can form.

생성자가 기록되지 않았습니다.

출처 CCC 2016 Senior