범죄 파티

용의자 $N$명이 있다. 용의자마다 친구가 정확히 2명 있다. 용의자는 모두 알리바이가 없어서 친구에게 거짓 알리바이 증언을 부탁한다. 부탁을 들어준 친구를 그 용의자의 변호인이라고 한다.

위증은 범죄라서 용의자는 친구에게 성의를 보여야 한다. 친구는 받은 성의를 수치로 환산하고, 만족하면 범죄에 협력해 변호인이 되어 준다. 친구가 만족하기 시작하는 수치를 임계값이라고 한다. 한 용의자의 두 친구도 친한 정도가 달라 임계값이 서로 다를 수 있고, 서로 다른 두 용의자와 친구인 사람은 용의자마다 임계값이 다를 수 있다.

웬만한 성의로는 꿈쩍하지 않는 친구를 움직이려고 용의자들은 파티를 연다. 파티에는 용의자의 친구가 모두 초대되고, 파티에 들인 비용이 클수록 만족하는 친구도 많아진다. 파티 비용이 $K$이면 임계값이 $K$ 이하인 친구는 모두 그 용의자의 변호인이 되어 준다.

용의자끼리는 서로를 변호하지 못하므로 용의자 집단과 친구 집단은 완전히 분리되어 있다. 한 사람이 여러 용의자를 변호하면 의심을 사기 때문에 한 사람은 최대 한 용의자의 변호인이 된다. 또 한 사람에게 용의자 친구는 최대 2명이다. 즉 서로 다른 용의자 $X_1$, $X_2$, $X_3$ 모두와 친구인 사람 $A$는 없다.

각 용의자의 친구 관계와 두 친구의 임계값이 주어질 때, 모든 용의자가 변호인을 1명 이상 두게 하는 최소 파티 비용 $K$를 구하라.

첫째 줄에 용의자의 수 $N$ ($1 \le N \le 200000$)이 주어진다. 다음 $N$개의 줄에는 $i$번째 용의자의 정보가 주어진다. 한 줄에 한 친구의 번호 $A_i$, 그 친구를 변호인으로 두기 위한 임계값 $KA_i$, 다른 친구의 번호 $B_i$, 그 친구의 임계값 $KB_i$가 차례로 주어진다. 친구 번호는 1 이상 $2N$ 이하이고, 임계값은 0 이상 1,000,000 이하의 정수다.

모든 용의자가 변호인을 두게 되는 최소 파티 비용 $K$를 출력한다. 어떤 비용으로도 불가능하면 -1을 출력한다.