Farmer John купил землю в Карибском регионе и собирается выращивать молочных коров на большой ферме из островов. По привычке он хочет окружить все острова оградой.

Каждый остров — многоугольник. Он огораживает по одной стороне между соседними вершинами, двигаясь по часовой стрелке. Чтобы окружить все острова, придётся в какой-то момент плавать к другим на лодке.

Можно начать с любой вершины. В любой встреченной вершине можно отправиться к вершине другого острова, огородить его целиком и НЕМЕДЛЕННО вернуться по тому же пути в ту же вершину исходного острова. Стоимость каждой поездки задана матрицей.

Острова описаны $N$ $(3 \le N \le 500)$ парами вершин $V1$,$V2$ $(1 \le V1 \le N; 1 \le V2 \le N)$; вы сами должны собрать их в острова. Вершины удобно пронумерованы $1,\ldots,N$.

Стоимость лодки между каждой парой вершин задана симметричной матрицей с элементами $0,\ldots,1000$.

Какова минимальная стоимость ограждения всех островов?

Входные данные

• Строка $1$: целое $N$.

• Строки $2,\ldots,N+1$: каждая описывает границу острова двумя целыми $V1$, $V2$ через пробел.

• Строки $N+2,\ldots,2\times N+1$: строка $i-N-1$ содержит $N$ целых строки $i$ матрицы стоимости: $Row_{i}$.

Выходные данные

• Строка $1$: целое, минимальная стоимость постройки ограды.

Примеры

Входные данные 1

12
1 7
7 3
3 6
6 10
10 1
2 12
2 9
8 9
8 12
11 5
5 4
11 4
0 15 9 20 25 8 10 13 17 8 8 7
15 0 12 12 10 10 8 15 15 8 8 9
9 12 0 25 20 18 16 14 13 7 12 12
20 12 25 0 8 13 14 15 15 10 10 10
25 10 20 8 0 16 20 18 17 18 9 11
8 10 18 13 16 0 10 9 11 10 8 12
10 8 16 14 20 10 0 18 20 6 16 15
13 15 14 15 18 9 18 0 5 12 12 13
17 15 13 15 17 11 20 5 0 22 8 10
8 8 7 10 18 10 6 12 22 0 11 12
8 8 12 10 9 8 16 12 8 11 0 9
7 9 12 10 11 12 15 13 10 12 9 0

Выходные данные 1

30

Примечание

  1        10            4
    xxxxxxx              x
   xxxxxxxxx            xxxx
7 xxxxxxxxxxx 6        xxxxxxx
 xxxxxxxxxxx       11 xxxxxxxxxx 5
  xxxxxxx
   xxx
  3         12 xxxxxxx 2
              xxxxxxxx
              xxxxxxxx
             xxxxxxxxx
             xxxxxxxxx
            xxxxxxxxxx
            xxxxxxxxxx
          8 xxxxxxxxxx 9

Пример задаёт три острова: $\{1,7,3,6,10\}$, $\{4,5,11\}$ и $\{2,9,8,12\}$. Цены заданы матрицей, например от $1$ до $2$ цена $15$.

Решение не единственно. FJ идёт от $3$ к $7$, останавливается в $1$, плывёт к $11$, затем проходит $4,5,11$. Возвращается в $1$, плывёт к $12$, далее $2,9,8,12$. Наконец возвращается в $1$ и продолжает $10,6,3,7$. Поездка от $1$ до $11$ и обратно стоит $8 \times 2 = 16$, от $1$ до $12$ и обратно $7 \times 2 = 14$, всего $30$.

Автор задачи: Fatih Gelgi, 2008