E - E Gym - 101492E (dp)

Teamwork is highly valued in the ACM ICPC. Since the beginning, the ICPC has distinguished itself from other programming contests in that teamwork is a key factor.

The University of Beijing, host of next year's World Finals, is planning recreational activities for the participants. They want to prepare games that show the importance of teamwork and enable new acquaintances among the contestants from all over the world. One of the staff members has been thinking about the following game.

In a court we have several N-person teams. The goal of each team is roughly as follows: starting from a corner, each team must take all of its members to the other corner of the court. The winning team is the one that finishes this in the shortest time.

Now we explain the game more formally. Consider the team that starts at corner A and must take all of its members to corner B. The following procedure is repeated:

1. While there are team members at corner A,
   • If there is only one team member, he is the only one that goes to corner B.
   • Otherwise, two team members must tie one leg of each with a rope and go to B.
2. Once arriving at B, they untie their legs, if applicable.
3. If there are still team members at corner A, some team member at B must return to A with the rope.

The organization wants to form the teams so that no team has an advantage. They entrusted you with the following task. Given the time in seconds that the members of a team take to go from a corner to the other, find the minimum time it takes for the team to take all its members from corner A to corner B. When two team members cross the court with their legs tied, the time for the pair to cross is the maximum between the times of the two members.

Input

The first line of input contains an integer N, the number of team members. The next line contains N integers ti, the time in seconds that the i-th team member takes to go from one corner to the other.

• 1 ≤ N ≤ 105
• 1 ≤ ti ≤ 109

Output

Print a single integer, the minimum time required for the whole team to reach corner B.

Examples

Input

3
30 40 50
      

Output

120
      

Input

4
10 20 50 100
      

Output

170
      

Note

In the first example, the process can be completed in 120 seconds as follows:

1. The first and second members go from A to B in 40 seconds.
2. The first member returns to corner A in 30 seconds.
3. The first and third team members go from A to B in 50 seconds.

This is not the only way to complete the process in this total time, but no other way does it in strictly less than 120 seconds.

題解：

我們先将所有人按花費時間遞增進行排序，假設前i個人過河花費的最少時間為opt[i]，那麼考慮前i-1個人過河的情況，即河這邊還有1個人，河那邊有i-1個人，并且這時候手電筒肯定在對岸，是以opt[i] = opt[i-1] + a[1] + a[i]        (讓花費時間最少的人把手電筒送過來，然後和第i個人一起過河)

如果河這邊還有兩個人，一個是第i号，另外一個無所謂，河那邊有i-2個人，并且手電筒肯定在對岸，是以opt[i] = opt[i-2] + a[1] + a[i] + 2*a[2]    (讓花費時間最少的人把電筒送過來，然後第i個人和另外一個人一起過河，由于花費時間最少的人在這邊，是以下一次送手電筒過來的一定是花費次少的，送過來後花費最少的和花費次少的一起過河，解決問題)

是以 opt[i] = min{opt[i-1] + a[1] + a[i] , opt[i-2] + a[1] + a[i] + 2*a[2] ；

代碼：

//Full of love and hope for life

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <vector>
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
//https://paste.ubuntu.com/
//https://www.cnblogs.com/zzrturist/    //部落格園
//https://blog.csdn.net/qq_44134712     //csdn

using namespace std;
const int N=5e3+10;
typedef long long ll;
const int mod=1e9+7;

ll n[100010],dp[100010];

int main(){
    ll a;
    cin >> a;
    for(ll i=1;i<=a;i++){
        cin >> n[i];
    }
    sort(n+1,n+a+1);
    dp[1]=n[1];
    dp[2]=n[2];
    for(ll i=3;i<=a;i++){
        dp[i]=min(dp[i-1]+n[1]+n[i],dp[i-2]+n[1]+n[i]+2*n[2]);
    }
    cout << dp[a];
    return 0;
}