The city of KOI consists of $N$ intersections and $N-1$ bidirectional roads, such that any two distinct intersections can be reached from each other using only these roads. In other words, the city's road network forms a tree structure. The roads are located on a 2D plane and do not intersect except at their endpoints. Each road has a non-negative integer weight.

Until a few decades ago, the city of KOI was a small village, but it began to expand rapidly as people moved in and it grew in size. During this rapid expansion, the mayor assigned numbers from $0$ to $N-1$ to the intersections for administrative convenience. This numbering system satisfies the following properties:

• Intersection $0$ is the center of the city and is guaranteed to be adjacent to at least two roads.
• The numbers assigned to the intersections correspond to one of the preorder traversals of the tree rooted at intersection $0$.
• For every intersection, consider the adjacent intersection (directly connected by a road) with the smallest number. If we list the numbers of the adjacent intersections in counter-clockwise order starting from this intersection, the numbers are in increasing order.

As many people moved into the city of KOI, traffic congestion became a serious problem. To solve this, the mayor connected the cities with the poorest transport infrastructure with a ring road. Let $\{V[0], V[1], \dots, V[K-1]\}$ be the list of intersections in the city of KOI that are adjacent to exactly one road, sorted in increasing order. The mayor constructed bidirectional roads connecting intersection $V[i]$ and intersection $V[(i+1) \pmod K]$ for all $0 \le i \le K-1$. The weight of each such road is a non-negative integer $W[i]$. Due to the nature of the numbering system, it is worth noting that the ring roads can be constructed such that no two roads intersect except at their endpoints.

The evil criminal gang "Dlalswp," based in the city of KOI, is causing much harm to the citizens. The mayor has deployed intelligence agents to catch the Dlalswp gang. According to the agents' intelligence, the Dlalswp gang defines a simple cycle of odd length as their criminal territory and commits crimes while traveling along that cycle.

To apprehend the notorious Dlalswp gang, the mayor intends to deploy police on the roads of the city of KOI such that every simple cycle of odd length has at least one road with police deployed on it. The cost to deploy police on each road is equal to the weight of the road. Calculate the minimum cost required for the mayor to achieve this goal.

Implementation Details

You must implement the following function:

long long place_police(vector<int> P, vector<long long> C, vector<long long> W)

• This function is called exactly once.
• $P$: An integer array of size $N-1$. It represents the original roads forming the city of KOI before the ring roads were built. For all $i$ ($0 \le i \le N-2$), there is a road connecting intersection $P[i]$ and intersection $i+1$.
• $C$: An integer array of size $N-1$. For all $i$ ($0 \le i \le N-2$), the weight of the road connecting intersection $P[i]$ and intersection $i+1$ is $C[i]$.
• $W$: An integer array of size $K$. For all $i$ ($0 \le i \le K-1$), the weight of the bidirectional road connecting intersection $V[i]$ and intersection $V[(i+1) \pmod K]$ is $W[i]$.
• This function must return the minimum cost to deploy police on the roads of the city of KOI such that every simple cycle of odd length has at least one road with police deployed on it.

You must not execute any input/output functions in any part of your source code.

Constraints

• $4 \le N \le 100\,000$
• $0 \le P[i] \le i$ for all $i$ ($0 \le i \le N-2$)
• $0 \le C[i] \le 10^{12}$ for all $i$ ($0 \le i \le N-2$)
• $0 \le W[i] \le 10^{12}$ for all $i$ ($0 \le i \le K-1$)

Subtasks

1. (6 points) $K \le 5$
2. (8 points) $P[i] = 0$ for all $i$ ($0 \le i \le N-2$)
3. (5 points) $C[i] \le 10^6$ for all $i$ ($0 \le i \le N-2$), $W[i] = 10^{12}$ for all $i$ ($0 \le i \le K-1$), and $K$ is even.
4. (15 points) $C[i] \le 10^6$ for all $i$ ($0 \le i \le N-2$), $W[i] = 10^{12}$ for all $i$ ($0 \le i \le K-1$).
5. (57 points) No intersection is adjacent to 4 or more roads.
6. (9 points) No additional constraints.

Examples

Input 1

4
0 9
0 8
0 0
9 9 9

Output 1

9

Note

The odd cycles in the city of KOI are $\{0, 1, 2\}$, $\{0, 2, 3\}$, $\{0, 3, 1\}$, and $\{1, 2, 3\}$. If the mayor deploys police on the road of weight $0$ connecting $(0, 3)$ and the road of weight $9$ connecting $(1, 2)$, every odd cycle will have at least one road with police deployed. The cost of this deployment is $0 + 9 = 9$, and it is impossible to achieve the goal with a lower cost.

Input 2

11
0 9
0 8
2 0
3 7
3 1
2 6
0 0
7 7
7 1
9 6
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000

Output 2

1

Note

If the mayor deploys police on the road of weight $0$ connecting $(2, 3)$, the road of weight $0$ connecting $(0, 7)$, and the road of weight $1$ connecting $(3, 5)$, every odd cycle will have at least one road with police deployed. The cost of this deployment is $0 + 0 + 1 = 1$, and it is impossible to achieve the goal with a lower cost.

Sample grader

The sample grader receives input in the following format:

• Line 1: $N$
• Line $2 + i$ ($0 \le i \le N-2$): $P[i] \ C[i]$
• Line $1 + N$: $W[0] \ W[1] \ \dots \ W[K-1]$

The sample grader outputs the following:

• Line 1: The value returned by the function place_police

Note that the sample grader may differ from the grader used in actual grading.