描述

有一个大晴天，小润与伙伴们一共 n 人春游，他们走到一条河边，想要过河到对岸。而岸边有一条小船。

船一次只能乘坐两人。每个人都有一个渡河时间 Ti，船划到对岸的时间等于船上渡河时间较长的人所用时间。

现在已知 n 个人的渡河时间 Ti，小润想要计算他们最少要花费多少时间，才能使所有人都过河。

注意，船上要有人才能坐上船划到对岸。

输入

二行，第一行是一个整数n(0<n<=100000)，为要过河的人数；第二行是n个整数Ti，为这n个人过河所需要的时间，两数之间以空格分隔。

输出

输出一行一个整数，为这n个人全部过河所花费的最少时间。

样例输入

10

1 4 3 2 9 7 18 22  23 3

样例输出

73