KOI 도시는 N개의 교차로와 N − 1개의 양방향 도로로 이루어져 있으며, 임의의 서로 다른 두 교차로를 도로만을 사용하여 오갈 수 있다. 즉, 도시의 도로망은 트리 구조를 이룬다.

도로는 2차원 평면 상에 있으며, 두 도로가 끝점을 제외한 위치에서 교차하지 않는다. 각 도로에는 0 이상의 정수 가중치가 존재한다.

KOI 도시는 몇십 년 전까지만 하여도 작은 마을이었지만, 사람이 유입되고 크기가 커지면서 급격히 팽 창하기 시작하였다.

급격한 팽창 과정에서 시장은 행정 편의를 위해 교차로에 0 이상 N − 1 이하의 번호를 매겼다. 이 때 번호 시스템은 다음과 같은 성질을 만족한다.

• 0번 교차로는 도시의 중심으로, 2개 이상의 도로와 인접함이 보장된다.

• 교차로에 매겨진 번호는 0번 교차로를 루트로 한 트리의 전위 순회 순서 (Preorder) 중 하나이다.

• 모든 교차로에 대해서, 인접한 (도로로 직접 연결된) 교차로 중 가장 번호가 작은 교차로를 생각해 보자. 이 교차로를 기준으로 반시계 방향으로 인접한 교차로의 번호를 나열했을 때, 번호는 증가한다.

KOI 도시에 많은 사람들이 유입되면서, 교통 체증 문제가 심화되었다. 시장은 이를 해결하기 위해 교통 인프라가 가장 빈약한 도시들을 외곽 순환 도로로 이었다.

KOI 도시에 있는 모든 교차로 중, 단 1개의 도 로와 인접한 교차로들의 번호를 증가하는 순서대로 나열한 리스트를 {V [0], V [1], . . . , V [K − 1]}라고 하자.

시장은, 모든 0 ≤ i ≤ K − 1에 대해서, V [i]번 교차로와 V [(i + 1) mod K]번 교차로를 잇는 양방향 도로를 건설하였다. 각 도로의 가중치는 0 이상의 정수 W[i]이다.

번호 시스템의 특성상, 두 도로가 끝점을 제외한 위치에서 교차하지 않게끔 외곽 순환 도로를 이을 수 있음을 관찰하면 좋다.

KOI 도시를 거점으로 하는 사악한 범죄단 Dlalswp은 시민들에게 많은 피해를 끼치고 있다. 시장은 Dlalswp 범죄단을 잡기 위해 정보요원들을 투입하였다.

정보요원들의 첩보에 의하면, Dlalswp 범죄단은 길이가 홀수 인 단순 사이클을 범죄 영역으로 설정하고, 해당 사이클을 돌면서 범죄 행위를 저지른다.

악명높은 Dlalswp 범죄단을 검거하기 위해, 시장은 모든 길이가 홀수인 단순 사이클에 경찰이 투입된 간 선이 하나 이상 있도록 KOI 도시의 도로에 경찰을 투입하려고 한다.

각 도로에 경찰을 투입하기 위해 필요한 비용은 도로의 가중치와 동일하다. 시장이 목표를 이루기 위해 필요한 최소 비용을 계산하여라.

제약 조건

• 4 ≤ N ≤ 100 000

• 모든 i에 대해 0 ≤ P[i] ≤ i (0 ≤ i ≤ N − 2)

• 모든 i에 대해 0 ≤ C[i] ≤ 1012 (0 ≤ i ≤ N − 2)

• 모든 i에 대해 0 ≤ W[i] ≤ 1012 (0 ≤ i ≤ K − 1)

외곽 순환 도로 2 timer 2s memory 1024MB

외곽 순환 도로 2 2s 1024MB