Problem1078--等待分配的程序

1078: 等待分配的程序

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 418  Solved: 184
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI有一台笔记本电脑,一台台式机电脑,两台电脑的性能相同,现在小明手里有N个等待运行的程序,每个程序运行所需的时间分别为n1,n2,n3,n4……,一台电脑同一时刻只能运行一个程序,一个程序只需要运行一次。两台电脑同时开始运行,请问小明该如何分配程序在这两台电脑上运行,使得最后结束运行的电脑的运行时间最短。

Input

输入不超过30组数据,每组数据第一行为N,代表有N个等待运行的程序,第二行为N个数字,代表每个程序的运行时间,1 <= N <= 1000 ,每个程序的运行时间均为正整数, 所有程序的运行时间之和不超过5000。

Output

输出最后结束运行的电脑的运行时间。

Sample Input

2
1 1
2
1 2
3
1 2 3

Sample Output

1
2
3

Source/Category