The Triangle Game

Time limit1sMemory limit128 MB

Summary
Given six triangles with numbered edges, rotate and arrange them into a hexagon where touching edges match, maximizing the sum of the six outer edges.
Level

Medium7 of 10

Topics
Backtracking, Brute force, Implementation, Simulation
Solved
No attempts yet

Problem

In the triangle game you start with six triangles, and every one of a triangle's three sides has a number written on it (see the figure). You must rotate and rearrange these triangles to assemble a single hexagon, subject to the rule that any two sides that touch each other must carry the same number. Triangles may be rotated but never flipped over. A completed hexagon looks like this:

The score is the sum of the numbers written on the six outer sides of the completed hexagon.

Given a set of triangles, determine the highest score that can be achieved with that set.

Input

The input consists of several sets.

Each set is given on six lines; each line describes one triangle with three integers between 1 and 100 inclusive. The three integers are the numbers on the triangle's sides, listed clockwise starting from the left side.

Each set is separated from the next by a line containing a single asterisk (*), and the final set is followed by a line containing a single dollar sign ($).

Output

For each set, in the order given, print one line: the highest achievable score if a hexagon can be formed, or none if it cannot.

Examples2

  1. Example 1

    Input
    1 4 20
3 1 5
50 2 3
5 2 7
7 5 20
4 7 50
*
10 1 20
20 2 30
30 3 40
40 4 50
50 5 60
60 6 10
*
10 1 20
20 2 30
30 3 40
40 4 50
50 5 60
10 6 60
$
    Expected output
    152
21
none

  2. Example 2

    Input
    10 1 20
20 2 30
30 3 40
40 4 50
50 5 60
60 6 10
$
    Expected output
    21