AK之旅

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

题目描述

他（她）沉迷游戏不能自拔，在比赛前的若干天偶然得知 $\, LZU \,$ 程序设计大赛，并了解到中意的妹子（汉子）也参加了这个比赛，从此浪子回头，采用最高效的方式学习算法，走上AK之旅（AK指比赛中的所有题都做对了）。

为简化难度，所有算法知识及其关系可以用一棵树来表示。这棵树有 $\, n \,$ 个节点，编号分别为 $\, 1,2,\dots,n \,$ 。对于编号为 $\, i \,$ 的节点，代表算法 $\, Algo_{i} \,$ ，如果掌握了算法 $\, Algo_{i} \,$ ，则有价值 $\, v_{i} \,$ 。根据树的定义，树有 $\, n-1 \,$ 条边，它们不构成回路，编号分别为 $\, 1,2,\dots,n-1 \,$ 。对于编号为 $\, j \,$ 的边，端点为 $\, x_{j},y_{j} \,$ （在树中， $x_{j}$ 是 $\,y_{j}\,$ 的父亲），长度为 $\, len(x_{j},y_{j}) \,$ ，代表如果掌握了算法 $\, Algo_{x_{j}} \,$ ，则可以花费 $\, len(x_{j},y_{j}) \,$ 的时间，掌握算法 $\, Algo_{y_{j}} \,$ 。在 $\, 0 \,$ 时刻，在爱的力量下，你掌握了根节点的算法，而其它算法暂时都不会。请问他在 $\, t \,$ 时刻后，最大的 $\, AK \,$ 值是多少（ $AK=\sum_{k=1}^{n}{v_{k}}*c_{k}$ ，如果掌握算法 $\, Algo_{k} \,$ ，则 $c_{k}$ 为1，否则 $c_{k}$ 为0）。

今天，他AK了所有的题目。

祝大家前程似锦，AK所有比赛！不过相比比赛，头发和妹子（汉子）才是最重要的哒！

输入描述:

第行，输入两个整数。

接下来行，第行输入一个整数。

接下来行，第行输入三个整数。

输出描述:

输出一个整数，为对应的最大的值。

示例1

输入

复制

输出

复制

说明


选择节点：

当前情况为满足条件下的值最大的情况。

题目描述

输入描述:

输出描述:

输入

输出

说明

备注: