#include<bits/stdc++.h> #define int long long #define lb(x) ((x)&(-(x))) #define ctz __builtin_ctzll #define pc __builtin_popcountll using namespace std; const int maxn=757; int n; int a[maxn]; priority_queue<int,vector<int>,greater<int> > q; inline void Greed(){ for(int i=1;i<=n;i++)q.push(a[i]); int ans=0; while(q.size()>1){ int P1=q.top();q.pop(); int P2=q.top();q.pop(); q.push(P1+P2); ans+=max(P1,P2)+2*min(P1,P2); } cout<<ans<<endl; return; } int dp[maxn]; int Sum[(1<<15)+7]; inline void DP(){ int U=(1<<n)-1; for(int S=1;S<=U;S++){ Sum[S]=Sum[S^lb(S)]+a[ctz(lb(S))+1]; } memset(dp,63,sizeof(dp)); for(int i=0;i<n;i++)dp[1<<i]=0; for(int S=1;S<=U;S++){ if(pc(S)<2)continue; for(int T=(S-1)&S;T;T=(T-1)&S){ int P1=Sum[T],P2=Sum[S^T]; dp[S]=min(dp[S],dp[T]+dp[S^T]+max(P1,P2)+2*min(P1,P2)); } } cout<<dp[U]<<endl; return; } signed main(){ // freopen("telegram.in","r",stdin); // freopen("telegram.out","w",stdout); cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; DP(); return 0; }