Mějme N lidí na břehu řeky. Každý člověk má nějakou rychlost a skupina se chce dostat přes řeku. Přejít řeku lze pouze po lávce, která neunese více jak dvě osoby. Přecházející dvojice lidí jde pouze tak rychle, jak jde pomalejší z nich. Zároveň s sebou musí nést louči, která jim svítí na cestu. Problém je, že louče je pouze jedna, a tak se vždy musí jeden člověk vrátit s loučí zpátky na první břeh.

Je jasné, jaké je řešení pokud je lidí méně jak tři. Pokud jsou právě tři, tak chceme vždy poslet nejrychlejšího s ostatníma dvěma členy skupiny. Pokud je lidí ještě více, je možné poslat dvojici nejrychlejších, jeden se pak vrátí a přenechá louči dvěma nejpomalejším. Ti přejdou spolu, a s loučí se vrátí druhý nejrychlejší člen.

vi a, dp;
ll cnt(ll pos){
    if(pos==0)return 0;
    if(pos==1)return a[0];
    if(pos==2)return a[1];
    if(~dp[pos])return dp[pos];
    ll res=cnt(pos-1)+a[pos-1]+a[0]);
    if(pos!=3) res=min(res, cnt(pos-2)+a[pos-1]+a[0]+2*a[1]);
    return dp[pos]=res;
}
int main() {
    ll N;cin>>N;
    a=vi(N);F(N)cin>>a[i];
    dp=vi(N+1, -1);
    sort(a.begin(),a.end());
    cout << cnt(N) << endl;
    return 0;
}