cho.sh

Dice

Given a die net and N, stack N^3 dice into an N x N x N cube and minimize the sum of numbers on the five visible faces.

Medium5ImplementationGreedyMathBrute forceInterviewNo attempts yetTime limit2sMemory limit128 MB

Problem

    +---+
    | D |
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
    | C |
    +---+

Each of the six faces of a die has one number written on it. Folding the net above makes a die whose numbers face outward.

You are given the numbers written at positions A, B, C, D, E, and F in the net.

Jimin has N^3 identical dice. He wants to rotate and stack them to make an N × N × N cube. The cube is placed on a table, so among its six outer faces, only the 5 faces other than the bottom are visible.

Given N and the six numbers on the die, find the minimum possible sum of all numbers written on visible faces.

Input

The first line contains a natural number N.

The second line contains the numbers written at A, B, C, D, E, and F in the diagram, in that order.

N is a natural number at most 1,000,000, and each number written on the die is a natural number at most 50.

Output

Print the minimum possible sum of the numbers written on visible faces.