两人加工N个零件，制作每个零件需要一定时间，且每个零件只能由一个人独立完成。例如N=4，四件模型完成时间分别为8,11,13,21分钟，此时有多种方案，最优方案为A制作1/4件用29分钟，B加工3、4两件用24分钟，共用时29分钟。

输入格式：第一行为一个整数N，表示有N个零件。第二行N个整数，表示制作每个零件分别用多长时间，数与数之间用空格分隔。

输出格式：一个整数（表示最小用时）

样例输入：3 12 18 9 样例输出：21