/// problem: https://acm.timus.ru/problem.aspx?space=1&num=1152

int Solve(int mask, int n, int sum)  /// 0 => destroyed
{
    if(mask == 0) return 0;
    int ans = 0;
    for(int i = 0 ; i < n ; i++)
    {
        int newMask = mask, newSum = sum;
        for(int j = 0 ; j < 3 ; j++)
        {
            int k = i + j;
            if(k >= n) k -= n;
            if( ( newMask & (1<<k) ) > 0 )
            {
                newMask ^= 1<<k;
                newSum -= arr[k];
            }
        }
        if(newMask != mask)
        {

            ans = min(ans, Solve(newMask, n, newSum) + newSum);
        }
    }
} /// O(2^n * n)


int main()
{
    cout<<Solve((1<<n) - 1, n, sum);

    dpp[0] = 0;

    for(int mask = 1 ; mask < (1<<n) ; mask++) /// all possible state
    {
        int sum = preCal[mask];
        int ans = 0;
        for(int i = 0 ; i < n ; i++)
        {
            int newMask = mask, newSum = sum;
            for(int j = 0 ; j < 3 ; j++)
            {
                int k = i + j;
                if(k >= n) k -= n;
                if( ( newMask & (1<<k) ) > 0 )
                {
                    newMask ^= 1<<k;
                    newSum -= arr[k];
                }
            }
            if(newMask != mask)
            {

//                ans = min(ans, Solve(newMask, n, newSum) + newSum);
                ans = min(ans, dpp[newMask] + newSum);
            }
        }
    }

    cout<<dpp[(1<<n) - 1];
}