题目描述

强哥要做 $N$ 道菜， 每道菜要用 $T_i$ 的时间。

现在他有两个烤箱(两个烤箱一模一样没有任何区别)，每个烤箱最多烤一盘菜，求强哥做好所有菜最少要用多少时间。

输入格式 (kaoxiang.in)

输入第一行一个正整数N,接下来跟着N个正整数代表每道菜的时间

$N$

$T_1$ $\ldots$ $T_N$

输出格式 (kaoxiang.out)

5
8 3 7 2 5

13

一共有5道菜，第1道菜和第5道菜8+5=13归第一个烤箱

第2道菜+第3道菜+第4道菜（3+7+2=12）归第二个烤箱

总时间为13

2
1000 1

1000

提示

• $1\ \leq\ N\ \leq\ 100$
• $1\ \leq\ T_i\ \leq\ 10^3$