种树
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

scimoon 种了一棵以1为根的有根树，树上的节点要么有两个儿子，要么是叶子节点，节点 i 有一个生命力 val_i

scimoon 心血来潮，决定修建枝桠

每次 scimoon 会选择一个树杈 u 进行修剪，要求这个节点有两个儿子，并且这两个儿子均为叶子节点

修建之后，u 的两个儿子都会被剪掉，而 u 变成了一个叶子节点

若用大园林剪，则会使

若用小园林剪，则会使

其中 ls_u 表示 u 的左儿子， rs_u 表示 u 的右儿子

scimoon 剪得上头，一不小心剪得只剩下了根节点，scimoon 预测到会发生这样的事，于是给根节点留下了最大的生命力

scimoon 力气不够，若共修建 m 次，则最多只能用 次大园林剪

聪明的你一定能算出根节点最后的生命力是多少

输入描述:

第一行一个整数 n

接下来 n 行，每行两个正整数，表示 ls_i 和 rs_i，若为 0 则表示没有该儿子

接下来一行 n 个整数 val_i，表示初始权值，不保证只有叶节点有权

输出描述:

一个整数，根节点最后的生命力
示例1

输入

复制 
5
3 4
0 0
2 5
0 0
0 0
1 2 3 4 5

输出

复制 
4

备注: