题目描述

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

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

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

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

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

请注意：每盆花每天只会被浇水 1 次，任何时刻两位同学不会同时为同一盆花浇水。一盆花只要有一个人在浇水，另一个人就会去浇其他花；如果无花可浇，那么另一个人就会休息等最后一盆花被浇完。本题假设，一盆花浇完水切换到另外一盆花浇水，这个切换过程不消耗时间。

输入格式

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

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

其中，N <= 1e6，每盆花的浇水时间不超过 1e4。

输出格式

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

样例输入

5
5
4
1
2
3

样例输出

8

样例解释

样例中共有 5 盆花，浇水时间分别为 5、4、1、2、3，最终所有花浇完的时间是 8，具体过程如下： 一开始两人都未开始浇水（结束时间均为 0）。小 A 优先选择剩余花中浇水时间最长的（5），小 A 的结束时间变为 0+5=5。 剩余花中浇水时间最长的是 4，此时小 A 还在浇水（结束时间 5），小 B 开始浇这盆，结束时间变为 0+4=4。 剩余花中浇水时间最长的是 3，此时小 A 的结束时间（5）比小 B 的（4）晚，小 B 先结束当前浇水，于是小 B 浇这盆，结束时间变为 4+3=7。 剩余花中浇水时间最长的是 2，此时小 A 的结束时间（5）比小 B 的（7）早，小 A 先结束当前浇水，于是小 A 浇这盆，结束时间变为 5+2=7。 最后剩下浇水时间为 1 的花，此时两人结束时间都是 7，小 A 优先选择，结束时间变为 7+1=8。 所有花浇完后，小 A 的最终结束时间是 8，小 B 是 7，因此最后一盆花浇完的总时间为 8。