Митя и Вася играют в интересную игру. У них есть подвешенное дерево из \(n\) вершин, пронумерованных числами от \(1\) до \(n\). В этом дереве вершина \(1\) является корнем, а родителем вершины \(i \ge 2\) является вершина \(p_i\) (при этом будем говорить, что вершина \(i\) — ребенок вершины \(p_i\)).
В каждой вершине дерева находятся печеньки, в вершине \(i\) находится \(x_i\) печенек. Чтобы съесть одну печеньку в вершине \(i\), нужно потратить \(t_i\) единиц времени. Также в игре есть одна фишка. Изначально она находится в корне дерева. Чтобы переместить фишку по ребру, соединяющему вершину \(i\) с ее родителем, нужно потратить \(l_i\) единиц времени.
Митя и Вася ходят по очереди, Митя начинает. На своем ходу Митя перемещает фишку из вершины, где она находится, в одного из ее детей. Вася на своем ходу может удалить какое-то ребро, ведущее из вершины, в которой стоит фишка, в одного из ее детей, или не удалять ничего.
На любом своем ходу Митя может закончить игру. После этого он двигает фишку вверх до корня, по пути съедая какие-то печеньки. Митя может потратить суммарно на спуск, подъем и поедание печенек не более \(T\) единиц времени. Обратите внимание, что в конце игры фишка всегда оказывается в корне: Митя не может оставить фишку ни в какой промежуточной вершине, даже если требуемое число печенек уже было съедено — он обязан переместить фишку в корень (и на каждое перемещение фишки по ребру из вершины \(v\) в ее предка он тратит \(l_v\) единиц времени).
Какое максимальное количество печенек Митя может съесть, независимо от действий Васи?
Выходные данные
Выведите одно целое число — максимальное число печенек, которое может съесть Митя.
Примечание
В первом примере Митя может первым ходом переместить фишку в вершину \(2\). В этом случае, как бы после этого не играл Вася, Митя сможет съесть не менее \(11\) печенек. Ниже приведен пример того, как могла происходить игра:
- Митя перемещает фишку в вершину \(2\).
- Вася отрезает ребро, ведущее в вершину \(4\).
- Митя перемещает фишку в вершину \(5\).
- Так как у вершины \(5\) нет детей, Вася не отрезает ничего.
- Митя заканчивает игру и поднимается наверх, по пути собирая печеньки (\(7\) в вершине \(5\), \(3\) в вершине \(2\), \(1\) в вершине \(1\)).
Митя тратит \(1+0\) времени на движение вниз, \(0+1\) на движение вверх, \(7\cdot 2\) чтобы съесть \(7\) печенек в вершине 5, \(3\cdot 3\) чтобы съесть \(3\) печеньки в вершине 2, \(1\cdot 1\) чтобы съесть \(1\) печеньку в вершине 1. Суммарное время равно \(1+0+0+1+7\cdot 2+3\cdot 3+1\cdot 1=26\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 26
1 5 1 7 7
1 3 2 2 2
1 1
1 1
2 0
2 0
|
11
|
|
2
|
3 179
2 2 1
6 6 6
1 3
2 3
|
4
|