Mitya has a rooted tree with $n$ vertices indexed from $1$ to $n$, where the root has index $1$. Each vertex $v$ initially had an integer number $a_v \ge 0$ written on it. For every vertex $v$ Mitya has computed $s_v$: the sum of all values written on the vertices on the path from vertex $v$ to the root, as well as $h_v$ — the depth of vertex $v$, which denotes the number of vertices on the path from vertex $v$ to the root. Clearly, $s_1=a_1$ and $h_1=1$.
Then Mitya erased all numbers $a_v$, and by accident he also erased all values $s_v$ for vertices with even depth (vertices with even $h_v$). Your task is to restore the values $a_v$ for every vertex, or determine that Mitya made a mistake. In case there are multiple ways to restore the values, you're required to find one which minimizes the total sum of values $a_v$ for all vertices in the tree.
-----Input-----
The first line contains one integer $n$ — the number of vertices in the tree ($2 \le n \le 10^5$). The following line contains integers $p_2$, $p_3$, ... $p_n$, where $p_i$ stands for the parent of vertex with index $i$ in the tree ($1 \le p_i < i$). The last line contains integer values $s_1$, $s_2$, ..., $s_n$ ($-1 \le s_v \le 10^9$), where erased values are replaced by $-1$.
-----Output-----
Output one integer — the minimum total sum of all values $a_v$ in the original tree, or $-1$ if such tree does not exist.
-----Examples-----
Input
5
1 1 1 1
1 -1 -1 -1 -1
Output
1
Input
5
1 2 3 1
1 -1 2 -1 -1
Output
2
Input
3
1 2
2 -1 1
Output
-1
import sys
input=sys.stdin.readline
import collections
from collections import defaultdict
n=int(input())
par=[ int(i) for i in input().split() if i!='\n']
suma=[int(i) for i in input().split() if i!='\n']
graph=defaultdict(list)
for i in range(n-1):
    graph[i+2].append(par[i])
    graph[par[i]].append(i+2)
#print(graph)
weight=[0]*(n+1)
weight[1]=suma[0]
queue=collections.deque([1])
visited=set()
visited.add(1)
ok=True
while queue:
    vertex=queue.popleft()
    for child in graph[vertex]:
        if child not in visited: 
            if suma[child-1]==-1:
                mina=[]
                if len(graph[child])==1:
                    mina=[0]
                else:   
                    for j in graph[child]:
                        if j!=vertex:
                            mina.append(suma[j-1]-suma[vertex-1])
                ans=suma[vertex-1]+min(mina)
                suma[child-1]=ans
                if suma[child-1]<suma[vertex-1]:
                    ok=False
                else:
                    weight[child]=(suma[child-1]-suma[vertex-1])
            else:
                if suma[child-1]<suma[vertex-1]:
                    ok=False
                else:
                    weight[child]=(suma[child-1]-suma[vertex-1])
            #print(child,vertex,weight,suma[child-1],suma[vertex-1])
            queue.append(child)
            visited.add(child)
#print(weight,ok,suma)
if ok==True:
    print(sum(weight))
else:
    print(-1)

import sys
input=sys.stdin.readline
import collections
from collections import defaultdict
n=int(input())
par=[ int(i) for i in input().split() if i!='\n']
suma=[int(i) for i in input().split() if i!='\n']
graph=defaultdict(list)
for i in range(n-1):
    graph[i+2].append(par[i])
    graph[par[i]].append(i+2)
#print(graph)
weight=[0]*(n+1)
weight[1]=suma[0]
queue=collections.deque([1])
visited=set()
visited.add(1)
ok=True
while queue:
    vertex=queue.popleft()
    for child in graph[vertex]:
        if child not in visited: 
            if suma[child-1]==-1:
                mina=[]
                if len(graph[child])==1:
                    mina=[0]
                else:   
                    for j in graph[child]:
                        if j!=vertex:
                            mina.append(suma[j-1]-suma[vertex-1])
                ans=suma[vertex-1]+min(mina)
                suma[child-1]=ans
                if suma[child-1]<suma[vertex-1]:
                    ok=False
                else:
                    weight[child]=(suma[child-1]-suma[vertex-1])
            else:
                if suma[child-1]<suma[vertex-1]:
                    ok=False
                else:
                    weight[child]=(suma[child-1]-suma[vertex-1])
            #print(child,vertex,weight,suma[child-1],suma[vertex-1])
            queue.append(child)
            visited.add(child)
#print(weight,ok,suma)
if ok==True:
    print(sum(weight))
else:
    print(-1)
