P1033 Mission 2 - F2 : pmurT Ques(2)

Problem Background

Radar finally gets to the country and is now meeting pmurT. pmurT gives Radar several questions for Radar to answer.

Radar answered all of them. Can you answer it?

Problem Statement

Here’s pmurT’s \(2^{nd}\) problem:

已知有一个正方体，\(6\) 个面标号 \(1\sim6\)（相对面编号和为 \(7\)）。它的 \(12\) 条棱各有一个值，第 \(i\) 面与第 \(j\) 面之间的棱的值为 \(A_{i,j}\)。现在将这个正方体剪开几条棱使其展开，问展开后连接各面的棱值的和最小是多少？

Constraints

• \(1 \le A_{i,j} \le 10^{10}\)
• All \(A_{i,j}\)s are different.

Input

\(A_{1,2}\ A_{1,3}\ A_{1,4}\ A_{1,5}\)
\(A_{2,3}\ A_{2,4}\ A_{2,6}\)
\(A_{3,5}\ A_{3,6}\)
\(A_{4,5}\ A_{4,6}\)
\(A_{5,6}\)

Output

Print the smallest sum.

Samples

Input 1

1 2 3 4
5 6 7
8 9
10 11
12

Output 1

17

Here is the Expanded Graph:

As the graph shows, the sum is \(3+4+1+7+2=17\). For there’re no other graphs with the sum smaller than \(17\), we should print \(17\).

Input 2

238 320 199 139
329 346 190
987 356
477 508
283

Output 2

1086

Here is the graph:

Input 3

38901984 32880093 39891093 29098248
32989889 33875588 18983277
22222222 45678299
67382919 99999999
11111111

Output 3

115290446

Hints

Hint 1

Check the samples. Did you realize something?

Hint 2

Check the samples again. This time figure out the answers by yourself. Did you realize something now?

Hint 3

Find the English Translation of “棱”. Did you realize something?

Hint 4

Figure out how many edges are left in the cube’s Expanded Graph. Compare it with the number of faces. Did you realize something?