F. Печеньки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Митя и Вася играют в интересную игру. У них есть подвешенное дерево из $$$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$$$ единиц времени).

Какое максимальное количество печенек Митя может съесть, независимо от действий Васи?

Входные данные

В первой строке находятся два числа $$$n$$$, $$$T$$$ — количество вершин в дереве и время, которое у него есть на это ($$$2\le n \le 10^5$$$; $$$1\le T\le10^{18}$$$).

Во второй строке находятся $$$n$$$ чисел $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$ — число печенек в каждой вершине ($$$1\le x_i\le10^6$$$). В третьей строке находятся $$$n$$$ чисел $$$t_1$$$, $$$t_2$$$, ..., $$$t_n$$$ — время, которое требуется, чтобы съесть одну печеньку в $$$i$$$-й вершине ($$$1\le t_i\le10^6$$$).

Далее следует $$$n - 1$$$ строка, которые описывают дерево. Для каждого $$$i$$$ от $$$2$$$ до $$$n$$$ в отдельной строке записаны два числа $$$p_i$$$ и $$$l_i$$$, где $$$p_i$$$ — родитель вершины $$$i$$$, а $$$l_i$$$ — время, которое требуется Мите для перемещения фишки вдоль ребра из вершины $$$i$$$ в ее родителя ($$$1\le p_i < i$$$, $$$0\le l_i \le 10^9$$$).

Выходные данные

Выведите одно целое число — максимальное число печенек, которое может съесть Митя.

Примеры
Входные данные
5 26
1 5 1 7 7
1 3 2 2 2
1 1
1 1
2 0
2 0
Выходные данные
11
Входные данные
3 179
2 2 1
6 6 6
1 3
2 3
Выходные данные
4
Примечание

В первом примере Митя может первым ходом переместить фишку в вершину $$$2$$$. В этом случае, как бы после этого не играл Вася, Митя сможет съесть не менее $$$11$$$ печенек. Ниже приведен пример того, как могла происходить игра:

  1. Митя перемещает фишку в вершину $$$2$$$.
  2. Вася отрезает ребро, ведущее в вершину $$$4$$$.
  3. Митя перемещает фишку в вершину $$$5$$$.
  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$$$.