暂无测试数据。

题目描述

兰姐姐是来自火星的女王。
相信你们一定对兰姐姐不熟悉，
她统领整个火星，
在各方面拥有最高权力。

很久很久以前，
兰爸爸是火星的国王，
去世以后，
两个女儿争夺王位。

火星上最聪明的人是辣椒酱，
他帮助兰姐姐夺得了王位，
而兰姐姐的姐姐 Horse countryxing 没有得到王位，
便离开火星前往地球修行。

宇宙有三大语言，M++，Marscal，E++，
其中地球的 E++ 速度最快。

兰姐姐智商不高，
因此有什么题目总喜欢问辣椒酱。

火星上的蒟蒻使用 Marscal 速度比兰姐姐的 M++ 跑的快。

火星上的蒟蒻（jǔ ruò）出了一道难题：

给出 \(N\) 个魔方，
每个魔方有一个完成时间，
现在要求完成魔方的总时间最短。

兰姐姐当然不能自己上，
于是她拉上了好朋友辣椒酱。
两个人共同完成 \(N\) 个魔方，
也就是把 \(N\) 个魔方分成两份（不一定相等），
使得完成时间最长的那份时间最短。
兰姐姐的结局烂不烂就掌握在你手里了。

输入

第一行，一个正整数 \(N\)
第二行，\(N\) 个正整数表示每个魔方的完成时间，每个数均小于等于 100。

输出

一个数表示最短的完成时间

样例输入

6
1 3 5 7 9 14

样例输出

20

数据范围限制

\(30\%\) 的数据： \(N \leq 5\)；
\(60\%\) 的数据： \(N \leq 25\)；
\(100\%\) 的数据：\(N \leq 100\)；每个魔方的复原时间不会大于 100。

来源

基础篇补充7.15