단신쓴짠

사람의 몸에는 안전한 음식과 위험한 음식을 구별할 방법이 필요하다. 사람의 혀는 단맛, 신맛, 쓴맛, 짠맛 네 가지 맛을 감지한다. 흔히 말하는 맛있다와 맛없다는 이 네 가지 맛의 조합과 개인의 기호에 따라 갈린다.

그런데 준표는 맛을 느끼지 못한다. 신 김치를 먹고도 시지 않다고 말하는 준표를 보고 이를 알아챈 서현이는 준표가 위험한 맛을 감지하지 못해 사고를 당할까 걱정했다. 서현이는 준표가 왜 맛을 느끼지 못하는지, 그리고 왜 자신의 미각이 정상이 아님을 인정하지 못하는지 조사하기 시작했고, 준표에게 1번부터 $N$번까지 번호가 붙은 미뢰 $N$개가 있다는 사실을 알아냈다.

준표의 미뢰는 서로 연결되어 1번 미뢰를 루트로 하는 이진 트리 하나를 이룬다. 연결된 미뢰 덩어리 하나가 미뢰집단 하나다. 보통 사람에게는 미뢰집단이 $X$개 이상 있다. 또 맛은 복합적이어서 미뢰집단은 미뢰가 $K$개 이상이어야 제 역할을 한다. 서현이는 미뢰 사이의 연결을 끊어서 준표도 보통 사람처럼 미뢰가 $K$개 이상인 미뢰집단을 $X$개 이상 갖게 하려고 한다. 미뢰가 $K$개 미만인 미뢰집단이 남아도 괜찮다. 그런 집단은 개수에 세지 않을 뿐이다.

연결을 끊을 때마다 그 연결의 세기만큼 준표의 다른 신경계가 손상을 입는다. A 미뢰와 B 미뢰의 연결이 서로에게 10만큼 영향을 주고 있다면, 이 연결을 끊었을 때 준표도 10만큼 고통을 받는다. 미각이 돌아와도 다른 감각이 상처를 입으면 준표가 더 힘든 삶을 살게 되므로, 서현이는 끊어야 하는 연결의 영향의 합, 즉 준표가 받을 고통의 합을 최소로 하고 싶다. 준표가 다시 맛을 느끼기 위해 받게 될 최소 고통의 합은 얼마인지 구하라.

첫 줄에 준표가 가진 미뢰의 개수 $N$ (1 ≤ $N$ ≤ 5,000), 미뢰집단 하나가 제 역할을 하는 데 필요한 최소 미뢰 개수 $K$ (1 ≤ $K$ ≤ 100), 보통 사람처럼 맛을 느끼는 데 필요한 정상 미뢰집단의 최소 개수 $X$ (1 ≤ $X$ ≤ 100)가 주어진다.

이어서 $N-1$개 줄에 걸쳐 $i$ (2 ≤ $i$ ≤ $N$)번 미뢰의 정보 $P_i$ (1 ≤ $P_i$ ≤ $N$), $C_i$ (0 ≤ $C_i$ ≤ 100,000)가 주어진다. 이는 $i$번 미뢰의 부모가 $P_i$번 미뢰이며, 이 둘 사이를 끊으면 $C_i$만큼의 고통이 발생한다는 뜻이다. 1번 미뢰는 루트이므로 정보가 주어지지 않는다.

준표가 다시 맛을 느끼기 위해 겪어야 하는 고통의 합의 최솟값을 출력한다. 어떻게 해도 준표가 미각을 되찾을 수 없으면 -1을 출력한다.

두 번째 예제에서는 2번 미뢰와 4번 미뢰 사이의 연결을 끊을 때 고통의 합이 가장 작다.