99991344 - 做饭
Time Limit : 1 秒
Memory Limit : 128 MB
高桥君要制作 N 道不同的菜肴，每道菜肴制作需要连续使用烤箱 T_i 分钟。不能同时为两道以上的菜肴使用同一个烤箱。
当有两个烤箱可供使用时，最快需要多少分钟才能制作完所有 N 道菜肴？不考虑除使用烤箱外的其他时间。
Input
输入将以以下格式从标准输入中给出：
N
T_1 T_2 ... T_N
制約
- 1\ \leq\ N\ \leq\ 100
- 1\ \leq\ T_i\ \leq\ 10^3
- 输入的所有值均为整数
Output
请输出答案。
Examples
Input
5 8 3 7 2 5
Output
13
Input
2 1000 1
Output
1000
Input
9 3 14 15 9 26 5 35 89 79
Output
138
Hint
Sample Explanation 1
例如，当两个烤箱的使用方式如下时，可以在 13 分钟内制作完所有菜肴：
- 第一个烤箱：按顺序制作菜肴时间 8 + 5 = 13。
- 第二个烤箱：按顺序制作菜肴时间 3 + 7 + 2 = 12。