Scanner

Time Limit : 2 sec, Memory Limit : 262144 KB

D: スキャナー / Scanner

問題文

ここに $N$ 枚の紙がある。あなたは $3$ 台のスキャナーを並列に用いることで、 全ての紙をスキャンしたいと考えている。それぞれの紙はスキャンにかかる時間が決まっており、 $i$ 番目の紙をスキャンするのにかかる時間は $T_i$ である。 紙をスキャンする順番は任意であるが、$1$ 台のスキャナーで複数の紙を同時にスキャンすることはできない。

全ての紙のスキャンが終了し、スキャンを行っているスキャナーがなくなるまでにかかる時間を最小化しなさい。

入力

$N$
$T_1$
$T_2$
$T_3$
$\vdots$
$T_N$

制約

$1 \leq N \leq 50$
$1 \leq T_i \leq 50$
入力は全て整数

出力

答えを $1$ 行で出力してください.

サンプル

サンプル入力1

4
1
1
1
1

サンプル出力1

2

サンプル入力2

9
15
20
27
4
10
7
34
30
36

サンプル出力2

61

サンプル入力3

6
20
18
46
16
9
48

サンプル出力3

55

Source: Ritsumeikan University Programming Camp 2016 , Day 1, Shiga, Japan, 2016-03-06