Teleportation Network Reconfiguration

Bessie is in a network composed of N nodes numbered \(1\dots N\) and \(2N\) teleporters numbered \(1\dots 2N\). Each teleporter connects two distinct nodes \(u\) and \(v\) (possibly with multiple teleporters connecting the same pair). For every node \(v\), you are given a list of four distinct teleporters \(p_v = [p_{v,1}, p_{v,2}, p_{v,3}, p_{v,4}]\) that are incident to it.

A position is described by an ordered pair \((v, p_{v,i})\) where \(1\le v\le N\) and \(1\le i\le 4\). There are two kinds of moves you can make:

1. Using the current teleporter: If you are at \((v, p_{v,i})\) and teleporter \(p_{v,i}\) connects \(v\) and \(u\), you can move to \((u, p_{v,i})\).
2. Switching teleporters at the same node: In every node, the initial configuration pairs \(p_{v,1}\) with \(p_{v,2}\) and \(p_{v,3}\) with \(p_{v,4}\). That is, if you are at \((v, p_{v,2})\), you can switch to \((v, p_{v,1})\) and vice‐versa; similarly for \(p_{v,3}\) and \(p_{v,4}\). No other switching is allowed.

Thus, there are \(4N\) positions in total but they might not all be mutually reachable via such moves. To help, you are allowed to reconfigure the teleporters incident to any node \(v\) at a cost of \(c_v\) monetary units. When you reconfigure node \(v\), you may arbitrarily rearrange its list \(p_v\); after rearrangement the pairing rule is applied in order (the first two teleporters are paired and the last two are paired).

For example, if you rearrange the list at node \(v\) to \([p_{v,3}, p_{v,1}, p_{v,2}, p_{v,4}]\), then at node \(v\):

• If you are at \((v, p_{v,1})\) you may switch to \((v, p_{v,3})\) and vice‐versa.
• If you are at \((v, p_{v,2})\) you may switch to \((v, p_{v,4})\) and vice‐versa.

Your task is to compute the minimum total cost required to modify the network (by reordering the lists at a subset of nodes) so that every position becomes reachable from every other position.

inputFormat

The first line contains an integer \(N\) (the number of nodes). The second line contains \(N\) integers \(c_1, c_2, \dots, c_N\) where \(c_v\) is the cost to reconfigure node \(v\). Then \(N\) lines follow. The \(v\)-th of these lines contains 4 distinct integers \(p_{v,1}, p_{v,2}, p_{v,3}, p_{v,4}\) (each between 1 and \(2N\)), the teleporters incident to node \(v\). It is guaranteed that every teleporter appears exactly twice in total.

outputFormat

Output a single integer: the minimum total cost (in monetary units) needed such that all \(4N\) positions become mutually reachable.

sample

2
5 7
1 2 3 4
1 2 3 4

5