13166번 - 범죄 파티

N명의 범죄 용의자가 있습니다. 각각의 용의자에게는 친구가 2명씩 있습니다. 모든 용의자 X는 알리바이가 없으므로 친구에게 거짓 알리바이 증언을 부탁하려고 합니다. 친구가 이에 협조할 경우, 해당 친구를 용의자 X의 변호인이라고 합니다. 한 사람에게 용의자 친구는 최대 2명까지만 존재합니다. 즉, 임의의 용의자 X₁, X₂, X₃와 모두 친구인 A는 존재하지 않습니다.

위증은 범죄기 때문에 용의자는 친구를 변호인으로 두기 위해 성의를 보여야 합니다. 친구들은 용의자가 그들에게 보인 성의를 수치화하여, 만족하면 그의 범죄에 협력하여 변호인이 되어줍니다. 이때 각 친구가 만족하기 시작하는 수치를 임계값이라고 합니다. 용의자와 그의 두 친구는 친한 정도가 다르므로 각 친구의 임계값은 서로 다를 수 있습니다. 또한, 서로 다른 용의자와 친구인 한 사람이 있다면, 각 용의자가 해당 친구를 변호인으로 두기 위한 임계값 역시 다를 수 있습니다.

웬만한 성의로는 꿈쩍하지 않는 친구들을 위해 용의자들은 파티를 열었습니다. 파티에는 용의자들의 모든 친구가 초대되었으며 파티를 열기 위해 들인 비용이 많을수록, 만족하는 친구들도 많아집니다. 파티 비용이 K라고 하면 변호인으로 두기 위한 임계값이 K이하인 친구들은 모두 해당 용의자의 변호인이 되어줍니다.

용의자끼리는 서로를 변호할 수 없으므로, 용의자 집단과 그들의 친구 집단은 완전히 독립적입니다. 한 사람이 여러 명의 용의자를 변호하게 되면 의심을 사므로, 한 사람은 최대 한 용의자의 변호인이 될 수 있습니다. 각 용의자의 친구 관계와 해당 친구들의 임계값이 주어질 때, 모든 용의자가 1명 이상의 변호인을 둘 수 있는 최소 파티 비용 K를 구하세요.

첫 번째 줄에는 용의자의 수 N(1 ≤ N ≤ 200,000)이 주어진다. 두 번째 줄부터 N개의 줄에는 i번째 용의자의 친구를 나타내는 정수 A_i와 해당 친구를 변호인으로 두기 위한 임계값 K_Ai, 또 다른 친구를 나타내는 정수 B_i와 해당 친구를 변호인으로 두기 위한 임계값 K_Bi가 주어진다. 모든 친구의 번호는 1보다 크거나 같고 2N보다 작거나 같으며, 임계값은 0보다 크거나 같고 1,000,000보다 작거나 같은 정수이다.

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