Crime Party

There are $N$ suspects, and each suspect has exactly two friends. No suspect has an alibi, so every suspect asks a friend for false alibi testimony. A friend who agrees is called a defender of that suspect.

Perjury is a crime, so a suspect has to show goodwill first. Each friend turns that goodwill into a number and agrees to help once the number satisfies them. The number at which a friend starts to be satisfied is that friend's threshold. The two friends of one suspect are close to the suspect in different degrees, so their thresholds can differ, and a person who is a friend of two different suspects can have a different threshold for each of them.

Ordinary goodwill moves nobody, so the suspects throw a party. Every friend of every suspect is invited, and the more the party costs, the more friends it satisfies. If the party costs $K$, then every friend whose threshold is at most $K$ agrees to defend the suspect who asked.

Suspects cannot defend each other, so the suspects and the friends form two separate groups. Defending several suspects draws suspicion, so one person defends at most one suspect. One person is a friend of at most two suspects, which means no person $A$ is a friend of three different suspects $X_1$, $X_2$, $X_3$.

Given the two friends of each suspect and their thresholds, find the smallest party cost $K$ that gives every suspect at least one defender.

The first line contains the number of suspects $N$ ($1 \le N \le 200000$). Each of the next $N$ lines describes suspect $i$ with four integers: a friend $A_i$, the threshold $KA_i$ for that friend, the other friend $B_i$, and the threshold $KB_i$ for that friend. Friend numbers are between 1 and $2N$, and every threshold is an integer between 0 and 1,000,000.

Print the smallest party cost $K$ that gives every suspect a defender. If no cost works, print -1.