The Triangle Game

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.

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 ($).

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.