Domino Puzzle

Time limit1sMemory limit128 MB

Summary

Add dominoes of minimum total pip-sum so that all pieces form one row with matching ends, an Eulerian path completion on values 1 to 6.

Level: Medium7 of 10
Topics: Graph, Shortest path, Minimum spanning tree, Math
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples4

Example 1
Input
```
6
6 1
1 5
5 5
5 2
2 4
4 2
```
Expected output
```
0
```
Example 2
Input
```
5
1 5
6 1
5 5
2 4
2 4
```
Expected output
```
6
```
Example 3
Input
```
2
1 2
2 3
```
Expected output
```
0
```
Example 4
Input
```
2
1 2
3 4
```
Expected output
```
4
```