from heapq import *
class Maxheap:
def __init__(_): _.h = []
def add(_, v): heappush(_.h, -v)
def top(_): return -_.h[0] if _.h else -10**18
def pop(_): return -heappop(_.h)
class Graph:
def __init__(_):
_.change = Maxheap() # increment slope at ...
_.a = _.y = 0 # last line has slope a, starts from y
_.dx = 0 # the whole graph is shifted right by ...
def __iadd__(s, o):
if len(s.change.h) < len(o.change.h): s,o = o,s
dx = s.change.top() - o.change.top()
s.a, s.y = s.a+o.a, s.y+o.y+(o.a*dx if dx>=0 else -s.a*dx)
for v in o.change.h: s.change.add(-v + o.dx-s.dx)
return s
def shiftx(_, v): _.dx+= v
def shifty(_, v): _.y+= v
def addleft(_, v):
if _.change.top() < v-_.dx:
dx = v-_.dx - _.change.top()
_.y+= _.a*dx
_.change.add(v-_.dx)
def addright(_, v):
if _.change.top() < v-_.dx:
dx = v-_.dx - _.change.top()
_.y+= _.a*dx; _.a+= 1
_.change.add(v-_.dx)
return
_.change.add(v-_.dx)
_.a+= 1; _.y+= _.change.top()-(v-_.dx)
def cutright(_):
v = _.change.pop(); rval = v+_.dx
dx = v-_.change.top()
_.a-= 1; _.y-= _.a*dx
return rval
input = __import__('sys').stdin.readline
range = xrange
MIS = lambda: map(int,input().split())
n = sum(MIS())
C = [0, 0]
adj = [[] for i in range(n+1)]
adj[0].append(1)
for i in range(n-1):
p, c = MIS()
C.append(c)
adj[p].append(i+2)
# dfs because python bad at recursion
dfsord = []
stack = [0]
while stack:
p = stack.pop()
for q in adj[p]: dfsord.append(q); stack.append(q)
del stack
# slope trick
graph = [None for i in range(n+2)]
for v in reversed(dfsord):
G = Graph()
if not adj[v]:
G.addleft(C[v])
G.addright(C[v])
graph[v] = G
continue
for u in adj[v]: G+= graph[u]
while G.a > 1: G.cutright()
s1 = G.change.pop()
s2 = G.change.pop()
G.change.add(s1+C[v])
G.change.add(s2+C[v])
graph[v] = G
print(G.y)
