Бесі розташована на мережі з \(N\) (\(2\le N\le 10^5\)) вершин пронумерованих \(1\ldots N\) і \(2N\) порталів пронумерованих \(1\ldots 2N\). Кожен портал з'єднує дві різних вершини \(u\) і \(v\) (\(u\neq v\)). Множина порталів може з'єднувати деяку пару вершин.

Кожна вершина \(v\) сусідня для чотирьох різних порталів. Список порталів вершини \(v\) задається як \(p_v=[p_{v,1},p_{v,2},p_{v,3},p_{v,4}]\).

Ваше поточне положення може бути представлене впорядкованою парою \((\text{current vertex}, \text{current portal})\); тобто парою \((v,p_{v,i})\) де \(1\le v \le N\) і \(1\le i\le 4\).

Ви можете використовувати одну з таких операцій для зміни свого поточного положення:

1. Змінити поточну вершину переміщенням через поточний портал.
2. Переключити поточний портал. У кожній вершині перші два портали у списку об'єднані в пару та останні два портали у списку також об'єднані в пару. Тому якщо Ваш поточний стан \((v,p_{v,2})\), то Ви можете переключитися щоб використовувати портал \((v,p_{v,1})\) і назад. Аналогічно, якщо Ваше поточне положення \((v,p_{v,3})\) Ви можете переключитися на портал \((v,p_{v,4})\) і назад. Ніякі інші перемикання не дозволені (наприклад, Ви не можете переключитись з порталу \(p_{v,2}\) на портал) \(p_{v,4}\)).

Усього є \(4N\) різних станів. На жаль, може не виявитися, що що будь-який стан можна досягти з будь-якого за допомогою послідовності заданих операцій. Тому, за ціну \(c_v\) (\(1\le c_v\le 1000\)) мунів ви можете зробити перестановку списку порталів сусідніх вершині \(v\), у будь-якому бажаному Вами порядку. Після цього перші два портали в списку об'єднуються в одну пару, а останні два портали - в іншу. пару.

Наприклад, якщо Ви переставили портали вершини \(v\) у порядку \([p_{v,3},p_{v,1},p_{v,2},p_{v,4}]\),

Це означає, що якщо Ви у вершині \(v\),

• Якщо Ви в порталі \(p_{v,1}\), Ви можете перейти на портал \(p_{v,3}\) і назад
• Якщо Ви в порталі \(p_{v,2}\), Ви можете перейти на портал \(p_{v,4}\) і назад
• Тепер Ви не можете перемикатися з порталу \(p_{v,1}\) на \(p_{v,2}\), або з порталу \(p_{v,3}\) на портал \(p_{v,4}\) і назад.

Обчисліть мінімальну кількість мунів, необхідних для модифікації мережі таким чином, щоб зробити досяжним кожен стан кожного стану. Гарантується, що тестові дані сконструйовано таким чином, що існує хоча б один спосіб такої модифікації мережі.

Формат вхідних даних

Перший рядок містить \(N\).

Кожен із наступних \(N\) рядків описує вершину. Рядок \(v+1\) містить 5 розділених одиночними пробілами цілих чисел \(c_v,p_{v,1},p_{v,2},p_{v,3},p_{v,4}\).

Гарантується, що для кожної \(v\) всі \(p_{v,1},p_{v,2},p_{v,3},p_{v,4}\) різні, і кожен портал з'являється у списках рівно двох вершин.

Формат вихідних даних

Один рядок містить мінімальну кількість мунів, що потрібні для модифікації мережі щоб уможливити досяжність кожного стану з іншого стану.

Приклад вхідних даних

5
10 1 4 8 9
11 1 2 5 6
12 9 10 2 3
3 4 3 6 7
15 10 8 7 5

Приклад вихідних даних

13

Достатньо зробити перестановку списків вершин \(1\) і \(4\). Це вимагає \(c_1+c_4=13\) мунів. Перестановки такі: \(p_1=[1,9,4,8]\) та \(p_4=[7,4,6,3]\).

ОЦІНЮВАННЯ:

• У тестах 2-4, \(c_v=1\) для всіх \(v\).
• У тестах 5-12 немає додаткових обмежень.