题目描述

$\red{FJ }$有$\red{n}$包干草，第$\red{i}$干草的重量是 $\red{s_i}$ ，他想旧能平均地将干草分给三个农场。

他希望分配后的干草重量最大值旧能地小，比如，$\red{b_1,b_2,b_3}$ 是分配后的三个值，假设 $\red{b_1≥}$ $\red{b_2≥}$ $\red{b_3}$ ，则他希望 $\red{b_1}$ 的值旧能地小。

请计算 $\red{b_1}$ 的最小值。

输入格式

第一行一个正整数 $\red{n}$。 接下来 $\red{n }$行，每行一个正整数表示重量。

输出格式

输出一行一个整数表示答案。

样例

输入样例

8 
14 
2 
5 
15 
8 
9 
20 
4

输出样例

26

提示

一种满足要求的分配方案是：

农场 $\red{1: 2,9,15，}$$\red{b_1 = 26}$

农场 $\red{2: 4,8,14，}$$\red{b_2 = 26}$

农场 $\red{3: 5,20，}$$\red{b_3 = 25}$

对于 $\red{100\%}$的数据，$\red{1≤}$$\red{n≤}$$\red{20，}$$\red{1≤}$$\red{s_i≤}$$\red{100}$