Портали#11238

Портали

1 секунда

128 мегабайтів

Легка

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

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

Ваше поточне положення можна описати впорядкованою парою (поточна вершина, поточний портал); тобто парою $(v, p_{v, i})$ (v, p_{v,i}), де $1 \leq v \leq n$ 1 \leq v \leq n і $1 \leq i \leq 4$ 1 \leq i \leq 4. Ви можете використовувати одну з наступних операцій для зміни свого поточного положення:

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

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

Наприклад, якщо ви переставите портали вершини $v$ в порядку $[p_{v, 3}, p_{v, 1}, p_{v, 2}, p_{v, 4}]$ [p_{v,3}, p_{v,1}, p_{v,2}, p_{v,4}], це означає, що якщо ви у вершині $v$ ,

Якщо ви в порталі $p_{v, 1}$ p_{v,1}, ви можете переключитися на портал $p_{v, 3}$ p_{v,3} і навпаки.
Якщо ви в порталі $p_{v, 2}$ p_{v,2}, ви можете переключитися на портал $p_{v, 4}$ p_{v,4} і навпаки.
Тепер ви не можете переключатися з порталу $p_{v, 1}$ p_{v,1} на $p_{v, 2}$ p_{v,2}, або з порталу $p_{v, 3}$ p_{v,3} на портал $p_{v, 4}$ p_{v,4} і навпаки.

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

Вхідні дані

Перший рядок містить $n$ ( $2 \leq n \leq 1 0^{5}$ 2 \leq n \leq 10^5).

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

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

Вихідні дані

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

Приклади

Приклад 1

Примітка

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