99991344 - 做饭

高桥君要制作 N 道不同的菜肴，每道菜肴制作需要连续使用烤箱 T_i 分钟。不能同时为两道以上的菜肴使用同一个烤箱。

当有两个烤箱可供使用时，最快需要多少分钟才能制作完所有 N 道菜肴？不考虑除使用烤箱外的其他时间。

输入将以以下格式从标准输入中给出：

N
T_1 T_2 ... T_N

制約

• 1\ \leq\ N\ \leq\ 100
• 1\ \leq\ T_i\ \leq\ 10^3
• 输入的所有值均为整数

请输出答案。

Sample Explanation 1

例如，当两个烤箱的使用方式如下时，可以在 13 分钟内制作完所有菜肴：

• 第一个烤箱：按顺序制作菜肴时间 8 + 5 = 13。
• 第二个烤箱：按顺序制作菜肴时间 3 + 7 + 2 = 12。