Bessie se encuentra en una red compuesta por ~N~ vértices numerados del ~1~ al ~N~ y ~2N~ portales numerados del ~1~ al ~2N~. Cada portal conecta dos vértices distintos, ~u~ y ~v~ ~(u \neq v)~. Varios portales pueden conectar el mismo par de vértices. Cada vértice ~v~ es adyacente a cuatro portales distintos. La lista de portales adyacentes a ~v~ viene dada por ~p_v = [p_{v,1}, p_{v,2}, p_{v,3}, p_{v,4}]~.

Tu ubicación actual se puede representar mediante un par ordenado (vértice actual, portal actual); es decir, un par ~(v, p_{v,i})~ donde ~1 \leq v \leq N~ y ~1 \leq i \leq 4~. Puedes usar cualquiera de las siguientes operaciones para cambiar tu ubicación actual:

1. Cambiar el vértice actual moviéndote a través del portal actual.

2. Cambiar de portal. En cada vértice, los dos primeros portales de la lista se emparejan, al igual que los dos últimos. Es decir, si tu ubicación actual es ~(v,p_{v,2})~, puedes cambiar al portal ~(v,p_{v,1})~, y viceversa. De forma similar, si tu ubicación actual es ~(v,p_{v,3})~, puedes cambiar al portal ~(v,p_v,4)~, y viceversa. No se permiten otros cambios (por ejemplo, no puedes cambiar del portal ~p_{v,2}~ al portal ~p_{v,4})~.

Hay ~4N~ ubicaciones distintas en total. Desafortunadamente, no todas las ubicaciones son accesibles desde todas las demás mediante una secuencia de operaciones. Por lo tanto, por un coste de ~c_v~ ~(1 \leq c_v \leq 1000)~ moonies, puedes permutar la lista de portales adyacentes a ~v~ en el orden que prefieras. Después de esto, los dos primeros portales de la lista se emparejan, al igual que los dos últimos.

Por ejemplo, si permutas los portales adyacentes a ~v~ en el orden ~[p_{v,3},p_{v,1},p_{v,2},p_{v,4}]~, esto significa que si te encuentras en el vértice ~v~:

• Si actualmente estás en el portal ~p_{v,1}~, puedes cambiar al portal ~p_{v,3}~ y viceversa.
• Si actualmente estás en el portal ~p_{v,2}~, puedes cambiar al portal ~p_{v,4}~ y viceversa.
• Ya no podrás cambiar del portal ~p_{v,1}~ al ~p_{v,2}~, ni del portal ~p_{v,3}~ al portal ~p_{v,4}~, ni viceversa.

Calcula la cantidad mínima total de moonies necesaria para modificar la red de manera que sea posible alcanzar cualquier ubicación desde cualquier otra. Se garantiza que los datos de prueba están construidos de tal forma que existe al menos una manera válida de modificar la red.

Entrada

La primera línea contiene ~N~ ~(2 \leq N \leq 10^5)~. Las siguientes ~N~ líneas describen cada una un vértice. La línea v+1 contiene cinco enteros separados por espacios: ~c_v, p_{v,1}, p_{v,2}, p_{v,3}, p_{v,4}~. Se garantiza que para cada ~v, p_{v,1}, p_{v,2}, p_{v,3}, p_{v,4}~ son todos distintos, y que cada portal aparece en las listas de adyacencia de exactamente dos vértices.

Salida

Una sola línea que contenga la cantidad mínima total de moonies necesaria para modificar la red y permitir el acceso a cualquier ubicación posible desde cualquier otra ubicación.

Ejemplo de Entrada

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

Ejemplo de Salida

13

Basta con permutar las listas de adyacencia de los vértices 1 y 4. Esto requiere un total de ~c_1+c_4=13~ nodos lunares. Podemos usar ~p_1=[1,9,4,8]~ y ~p_4=[7,4,6,3]~.

USACO 2021 US Open, Gold Problem 2. Portals.