Under construction

Still being built. Things may change

The Triangle Game

Time limit2sMemory limit512 MB

Summary
Given six numbered triangles, arrange all of them into a legal hexagon where touching edges match, and maximize the sum of the six outer edge numbers.
Level

Medium6 of 10

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

Problem

The triangle game starts with six triangles that carry a number on each edge. The picture above is one example. You may slide and rotate the triangles so that they form a hexagon, but the hexagon is legal only when the edge shared by two neighboring triangles has the same number on both of them. Flipping a triangle over is not allowed. The picture below shows two legal hexagons built from the same six triangles.

The score of a legal hexagon is the sum of the numbers on its six outer edges.

Given six triangles, find the highest score that can be reached.

Input

The input holds one or more data sets. One data set is six lines, and each line has three integers from 1 to 100 separated by blanks. The three numbers on a line are the numbers on the edges of one triangle in clockwise order. A line holding only an asterisk (*) separates two data sets, and a line holding only a dollar sign ($) follows the last data set. There are at most 200 data sets.

Output

Print one line for each data set. Print none when no legal hexagon exists, otherwise print the highest score.

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
    1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
$
    Expected output
    6