该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

由于石老师发现比赛中小学生用开 avx512f 的赖皮写法把防 AK 题给过了。石老师决定加强数据后重测。

睿爸的判题服务器是一个双核的 CPU ，意味着可以同时判两个提交。第 $i$ 次提交的判别时间为 $a_i$ ，假设判题可以不按照提交时间乱序执行，问最坏情况下重测所有提交需要多少时间？

在单核 CPU 上总的判题时间不超过 $\leq 5000000$ 。

Format

Input

第一行包含一个整数 $n$ $(1 \leq n \leq 10^6)$，表示提交数。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，表示每个提交需要耗费的评测时间。

Output

输出一个整数，表示重测需要耗费的最长时间。

Samples

3
1 2 3

4

Limitation

1s, 1024KiB for each test case.