Портали

Бесі розташована на мережі з n вершин, позначених від 1 до n, і 2n порталів, позначених від 1 до 2n. Кожен портал з'єднує дві різні вершини u і v (u ≠ v). Множина порталів може з'єднувати одну й ту ж пару вершин.

Кожна вершина v має чотири різні портали. Список порталів вершини v задається як p[v] = p[v,1], p[v,2], p[v,3], p[v,4].

Ваше поточне положення можна описати впорядкованою парою (поточна вершина, поточний портал); тобто парою (v, p[v,i]), де 1 ≤ v ≤ n і 1 ≤ i ≤ 4. Ви можете використовувати одну з наступних операцій для зміни свого поточного положення:

• Змінити поточну вершину, переміщуючись через поточний портал.

• Перемкнути поточний портал. У кожній вершині перші два портали в списку об'єднані в пару, і останні два портали в списку також об'єднані в пару. Тому, якщо ваше поточне положення (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 ≤ c[v] ≤ 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 (2 ≤ n ≤ 10^5).

Кожен з наступних 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] різні, і кожен портал з'являється в списках рівно двох вершин.

Вихідні дані

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

Приклад

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

Приклади