题目描述

津津可以同时用左右手独立做题，每次选择最上面的题目。求完成所有题目的最短时间。

输入格式

• 第一行：整数$n$（题目数量）
• 接下来$n$行：每行一个整数$time_i$（第$i$题所需时间）

输出格式

完成所有题目的最短时间（整数）

样例

输入

4
2
3
3
3

输出

6

数据范围与提示

• 数据规模：
  • $0 \leq n \leq 10^3$
  • $0 \leq time_i \leq 10^9$
• 特殊数据分布见原题描述
• 最优安排策略：将题目时间分为两组，最短时间为两组中较大者