该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师最近在玩一款名为《单人成行》的探索游戏

这天他碰到了一个关卡，这个关卡中有 $n$ 个房间，由 $n-1$ 条走廊连接，保证任意两个房间都可以互相到达。

徐老师出生在 $1$ 号房间，除了 $1$ 号房间以外每个房间都有一个结界，打破编号 $i$ 房间的结界会让徐老师受到 $a_i$ 点伤害（扣除 $a_i$ 点血量），每个房间的结界被打破以后就可以随意进出该房间，不再受到二次伤害

徐老师可以进入所有被打破结界的房间，获得这个房间的道具，编号 $i$ 房间的道具可以让徐老师回复 $b_i$ 点血量，当然每个房间的道具也只能使用一次

徐老师不能进入到有结界的房间，也不能穿过有结界的房间到达其他房间。

例如现在有四个房间如下

    1
   / \
  2   4
 /     \
3       5

徐老师想要去到 $3$ 号房间，就必须先打破 $2$ 号房间的结界，穿过 $2$ 号房间，再打破 $3$ 号房间的结界，才能进入 $3$ 号房间

当然，徐老师也可以选择先打破 $2$ 号房间的结界，再打破 $4$ 号房间的结界，再回头打破 $3$ 号房间的结界

徐老师的初始血量有 $x$，当然，在任何时刻徐老师的血量都不可以为负数（可以为 $0$)

徐老师想知道，在过程中，他的血量最多能达到多少？

其中，石老师又提出了加强版需求：如果需要获取所有房间的道具，初始血量最少可以是多少？

输入格式

输入第一行包含三个整数 $n, x, st$，其中 $st$ 用于判断是否需要回答石老师的问题

接下来 $n-1$ 行每行包含两个整数 $u, v$ ，表示编号 $u$ 和 $v$ 的房间之间存在一条走廊连通

接下来 $n-1$ 行每行包含两个整数 $a_i, b_i$ ，依次表示编号 $2 \sim n$ 的房间对应 $a_i$ 和 $b_i$

输出格式

输出第一行包含一个数字，表示初始血量为 $x$ 时，过程中血量最多能达到多少

如果 $st == 1$ 则需要输出第二行，包含一个数字，表示获得所有房间道具所需要的最少初始血量

数据范围

对于 $20\%$ 的数据保证 $n\leq 500000, st=1$，且为一条链。

对于另外 $40\%$ 的数据保证 $n\leq 500000, st=0$ 。

对于另外 $40\%$ 的数据保证 $n\leq 500000, st=1$ 。

对于所有数据保证 $x, |a_i|, |b_i| \leq 10^9$。

输入样例

3 10 1
1 2
1 3
10 11
11 5

输出样例

11
10

样例解释

先打破 $2$ 号房间的结界，受到 $10$ 点伤害，血量为 $0$，进入房间获得道具，血量变为 $11$，此时血量达到最高

接着再打破 $3$ 号房间的结界，受到 $11$ 点伤害，血量为 $0$，进入房间获得道具，血量变为 $5$

所以初始血量最少需要 $10$ 点即可获得所有房间的道具