The Share

Three brothers are about to work in their father's shop for a period of time. The shop is doing well, and every day it generates a profit that the three brothers can predict. The brothers have agreed to divide the total time into three consecutive segments, not necessarily of equal duration. Each brother will work in the shop during one of these segments and will receive the corresponding profit for himself.

However, they want to make the distribution fair so that none of the three brothers receives much more profit than the others. Specifically, they want to minimize the profit that the most favored among the three can receive.

Problem

Write a program in one of the IOI languages that, given the number N of days the three brothers will work and the predicted profit for each of these days, finds the minimum profit that the most favored of the three brothers can receive.

Input Files:

The input files named share.in are text files with the following structure: The first line contains an integer N ~(3 \le N \le 1.000.000)~, the number of days. The following N lines contain the predicted profits for each of these days, which are integers V~\mathbf{_i}~ ~(1 \le V_i \le 100.000.000)~. Consider that the total profit (i.e., the sum of all ~V_i~) does not exceed ~1.000.000.000~.

Output Files:

The output files named share.out are text files with the following structure: They have only one line containing exactly one integer, the minimum profit that the most favored of the three brothers can receive.

Examples of Input - Output Files:

1st

STDIN (share.in)

8
5
6
1
4
9
3
1
2

STDOUT (share.out)

13

Explanation of the first example: In the fairest possible share, the first brother will work for three days and will receive a profit of ~5+6+1=12~. The second brother will work for two days and will receive a profit of ~4+9=13~, and the third brother will work the remaining three days and will receive a profit of ~3+1+2=6~. The most favored will be, of course, the second brother.

2nd

STDIN (share.in)

10
1
1
8
1
1
3
4
9
5
2

STDOUT (share.out)

15

Explanation of the second example: In the fairest possible share, the first brother will work for six days and will receive a profit of ~1+1+8+1+1+3=15~. The second brother will work for two days and will receive a profit of ~4+9=13~, and the third brother will work the remaining two days and will receive a profit of ~5+2=7~. The most favored will now be the first brother.

Maximum Execution Time: 1 sec