Dice

Interview

Time limit2sMemory limit128 MB

Summary

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.

Level: Medium5 of 10
Topics: Implementation, Greedy, Math, Brute force
Solved: No attempts yet

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.

Examples4

Example 1
Input
```
2
1 2 3 4 5 6
```
Expected output
```
36
```
Example 2
Input
```
3
1 2 3 4 5 6
```
Expected output
```
69
```

Example 3

Input

1000000
50 50 50 50 50 50

Expected output

250000000000000

Example 4
Input
```
10
1 1 1 1 50 1
```
Expected output
```
500
```