题目描述

Ante 和 Goran 正在准备 $n$ 个团队。他们每个人各有一个算法需要向所有团队讲解。

当然，他们不能两人同时对同一个团队讲解，也不能同时对多个团队讲解。

给定对每个团队讲解所需的时间，你需要确定讲解所需的最少时间。

输入格式

第一行输入包含整数 $n$，即团队数量。

下一行包含 $n$ 个空格分隔的整数 $a_i$，表示对第 $i$ 个团队讲解所需的时间。

输出格式

仅一行，即讲解所需的最少时间。

3
2 2 2

6

3
4 1 2

8

4
1 3 2 1

7

提示

样例 1 说明

每个团队都需要 $2$ 个单位时间来理解和实现一个算法，以下是一种可行的授课方法。

样例 2 说明

其中一种最佳的时间安排是 Ante 依次给团队 $2,3, {\color{red}x},1$ 讲解，但是在 $\color{red}x$ 中有一个 $1$ 个单位时间的暂停。Goran 将依次给团队 $1,3,2$ 讲课。

数据规模与约定

• 对于 $40\%$ 的数据，有 $1\le n\le 7$。
• 对于 $100\%$ 的数据，有 $1\le n\le 3\times 10^5$。

对于所有合法的 $a_i$，都有 $a_i\in [1,3\times 10^5]$。

说明

题目译自 COCI2014-2015 CONTEST #4 T3 PRIPREME。