当前没有测试数据。

养花

题目描述

学校的花圃里种了 $N$ 盆花，不同的花需要的水量不同，因此浇水时间也就不同了。

三年级四班的小 $A$ 和 小 $B$ 两位同学来为花浇水，他们都很热爱劳动，都想为浇水时间长的花浇水，负担更多的劳动。

小 $A$ 是劳动委员，也比小 $B$ 强壮一些，在集体劳动面前，他总是会挑最费力、最耗时的活来干。

在这次浇花中，小 $A$ 会优先挑浇水时间最长的花来浇水，小 $B$ 则会挑浇水时间次长的花来浇水，当一盆花浇完，他们就会立刻去浇剩余的花中，浇水时间最长的花。如果两个人同时浇完自己选的花，那么小 $A$ 会优先在剩余的花中挑选下一盆要浇的花。

已知 $N$ 盆花，每盆花的浇水时间，请编程计算出最后一盆花浇完，需要多长时间。

请注意：每盆花每天只会被浇水 $1$ 次，任何时刻两位同学不会同时为同一盆花浇水，一盆花只要有一个人在浇水，另一个人就会去浇其他花，如果无花可浇，那么另一个人就会休息等最后一盆花被浇完。

本题假设，一盆花浇完水切换到另外一盆花浇水，这个切换过程不消耗时间。

输入

第 $1$ 行读入整数 $N$，代表花的总数。

第 $2$ 到 $N+1$ 行，每行有一个整数，代表每盆花的浇水时间。

输出

输出一个整数，代表所有的花都浇完水的时间。

样例

输入复制

2
5
10

输出复制

10

输入复制

5
1 
1 
3 
7 
12

输出复制

12

输入复制

3
7 
5 
3

输出复制

8

说明

样例 $1$ 说明

共有 $2$ 盆花，小 $A$ 选择了第 $2$ 盆花需要 $10$ 分钟，小$B$ 浇第 $1$ 盆花需要 $5$ 分钟。因此两盆花都浇完，最少需要 $10$ 分钟。

样例 $2$ 说明

共有 $5$* 盆花，小 $A$ 浇第 $5$ 盆花需要 $12$ 分钟；小 $B$ 浇前 $4$ 盆花，共需 $1+1+3+7=12$ 分钟。因此所有花都浇完，需要 $12$ 分钟。

数据范围

对于 $30$% 的数据保证： $1≤n≤100$ 。

对于 $70$% 的数据保证： $1≤n≤10^{5}$ 。

对于 $100$% 的数据保证： $1≤n≤10^{6}$，每盆花的浇水时间在 $[1,104]$ 的范围内。