[USACO12JAN] Bale Share S

题目描述

FJ 有 $n$ 包干草,第 $i$ 干草的重量是 $s_i$,他想尽可能平均地将干草分给三个农场。 他希望分配后的干草重量最大值尽可能地小,比如,$b_1,b_2,b_3$ 是分配后的三个值,假设 $b_1 \ge b_2 \ge b_3$,则他希望 $b_1$ 的值尽可能地小。 请计算 $b_1$ 的最小值。

输入输出格式

输入格式


第一行一个正整数 $n$。 接下来 $n$ 行,每行一个正整数表示重量。

输出格式


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

输入输出样例

输入样例 #1

8 
14 
2 
5 
15 
8 
9 
20 
4 

输出样例 #1

26 

说明

【样例解释】 一种满足要求的分配方案是: 农场 1: $2,9,15$,$b_1 = 26$ 农场 2: $4,8,14$,$b_2 = 26$ 农场 3: $5,20$,$b_3 = 25$ 【数据范围】 对于 $100\%$ 的数据,$1\le n \le 20$,$1 \le s_i \le 100$。