题目描述

Alice 和 Bob 在一棵以 $0$ 为根的二叉树上进行游戏。这里“二叉树”只表示每个结点最多有两个儿子。

共有 $N$ 个结点，编号为 $0$ 到 $N-1$。对于 $0\le i<N-1$，结点 parent[i] 与结点 $i+1$ 之间有一条无向边，删除这条边需要支付 cost[i] 的代价。没有儿子的结点称为叶子。

Bob 的棋子初始位于结点 $0$。每一步：

1. Bob 选择一条与当前棋子位置相邻、且仍可使用的边；
2. Alice 可以选择永久删除这条边并支付对应代价，此时 Bob 本步不移动；
3. 如果 Alice 不删边，Bob 就沿这条边移动到另一端。

每条边最多可以被 Bob 使用两次，并且两个方向各至多一次。

如果 Bob 的棋子到达任意叶子，Alice 立即失败；如果 Bob 已经没有任何合法移动，则 Alice 获胜。

Alice 总能获胜。Alice 希望自己支付的总代价尽可能小，而 Bob 希望这个代价尽可能大。双方均采用最优策略，求最终 Alice 需要支付的总代价。

输入格式

第一行输入整数 $M=N-1$。

接下来 $M$ 行，第 $i+1$ 行输入两个整数 parent[i] 和 cost[i]，表示结点 parent[i] 与结点 $i+1$ 之间的边及其删除代价。

输出格式

输出一个整数，表示双方最优策略下 Alice 最终支付的总代价。

数据范围

• $2\le N\le100$；
• $0\le \text{parent}[i]\le i$；
• $1\le \text{cost}[i]\le10000$；
• 整棵树以 $0$ 为根时，每个结点最多有两个儿子。

样例

2
0 3
1 5

3

说明

Alice 必须阻止 Bob 到达叶子 $2$。她可以删除边 $0-1$ 或边 $1-2$，最优选择是支付 $3$ 删除前者。