Domino Puzzle

You are given a set of dominoes. Each domino is a rectangular piece marked with two numbers, each between $1$ and $6$ (the two numbers may be equal). The dominoes can be arranged in a single row so that the touching ends of two adjacent pieces show the same number. A domino may be flipped, so the order of the two numbers on a piece can be chosen freely.

Some sets can be arranged into such a row using every piece exactly once; others cannot. For example, the set of five pieces $(1,5), (1,6), (5,5), (2,4), (2,4)$ cannot be arranged into a single row.

To make an un-arrangeable set arrangeable, you may add extra dominoes (each again marked with two numbers between $1$ and $6$). Adding a piece has a cost, and the cost of a piece is the sum of its two numbers. Among all sets of extra pieces that make the whole collection (original plus added) arrangeable into one row, you want the one whose total cost is as small as possible. If the original set can already be arranged into a single row, the added set may be empty, in which case its cost is $0$.

Given a domino set, output the smallest possible total cost of an additional set of dominoes such that all pieces (original plus added) can be laid out in a single row.

The first line contains the number of pieces $N$ ($2 \le N \le 100$) in the given set. Each of the next $N$ lines contains two integers between $1$ and $6$, separated by a space, describing one piece. The two numbers of a piece may be given in either order.

Print a single integer: the smallest possible value of the total sum, over all pieces of an additional set, of each piece's two numbers, such that the whole collection can be laid out in a single row. Print $0$ if no extra piece is needed.