Преступная сеть
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Оказалось, что текущее дело сильно интереснее, чем казалось Бенуа Бланку в начале — вовлечен крупнейший клан мафии города. К счастью, в этот раз мафия не связана с преступником, а сама пострадала от его действий, поэтому детективу необходимо наладить с ними сотрудничество.

Известно, что кланом управляют $$$n$$$ самых важных ее членов, между которыми есть четкая иерархия в виде подвешенного дерева. Во главе клана стоит лидер под номером $$$1$$$, а у каждого из оставшихся $$$n - 1$$$ члена управления есть свой непосредственный босс: босс члена номер $$$i$$$ имеет номер $$$p_i$$$.

Помимо этого, у $$$i$$$-го из $$$n$$$ людей из руководства есть $$$a_i$$$ рядовых «шестерок» в непосредственном подчинении (множества «шестерок» разных членов руководства не пересекаются).

Прямо сейчас Бланку нужно срочно передать важное сообщение, которое должно дойти до как можно большего числа людей, состоящих в клане. Известно, что как только человек получает сообщение, он передает его всем своим непосредственным подчиненным. «Шестерки» получают сообщение от своего руководителя моментально, а член руководства номер $$$i$$$ получает сообщение от своего босса за $$$t_i$$$ минут.

Время поджимает, поэтому у Бенуа Бланка есть ровно $$$T$$$ минут, и всего лишь один звонок любому из $$$n$$$ членов руководства. Помогите ему выбрать, кому следует позвонить, чтобы за $$$T$$$ минут сообщение достигло как можно большего числа людей.

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

В первой строке через пробел даны два целых числа $$$n$$$ и $$$T$$$ — количество людей в руководстве и ограничение на время распространения сообщения ($$$1 \leqslant n \leqslant 10^5$$$; $$$0 \leqslant T \leqslant 10^9$$$).

В следующей строке через пробел перечислены целые числа $$$p_2$$$, ..., $$$p_n$$$ — номера непосредственных боссов членов руководства с номерами от $$$2$$$ до $$$n$$$ ($$$1 \leqslant p_i \leqslant n$$$). Гарантируется, что иерархия представляет собой дерево, подвешенное за вершину $$$1$$$.

В третьей строке ввода через пробел перечислены целые числа $$$t_2$$$, ..., $$$t_n$$$ — время, необходимое, чтобы сообщение дошло до соответствующего члена руководства от его непосредственного босса ($$$0 \leqslant t_i \leqslant 10^9$$$).

В последней стороке в том же формате перечислены $$$n$$$ целых чисел $$$a_i$$$ — количество «шестерок» у каждого члена руководства ($$$0 \leqslant a_i \leqslant 10^9$$$).

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

Выведите через пробел два целых числа — номер человека из руководства, которому Бенуа следует позвонить, и суммарное число людей, которые получат сообщение за $$$T$$$ минут.

Если оптимальных ответов несколько, выведите любой из них.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
116$$$n \leqslant 1000$$$полная
216$$$p_i = i - 1$$$ для всех $$$i$$$полная
310$$$T \leqslant 10$$$; $$$t_i = 1$$$ и $$$a_i = 0$$$ для всех $$$i$$$полная
416$$$T \leqslant 10$$$3первая ошибка
520$$$a_i = 0$$$3первая ошибка
622нет1 – 5первая ошибка

Примеры

Входные данные
3 10
1 1
9 11
100 49 51
Выходные данные
1 151
Входные данные
7 15
1 1 2 2 3 3
9 8 6 9 16 5
400 100 200 50 1000 1100 300
Выходные данные
2 1153

Примечание

В первом примере следует звонить главе клана. За $$$10$$$ минут сообщения достигнут его, члена руководства номер $$$2$$$, и еще $$$100 + 49$$$ их «шестерок», то есть всего $$$151$$$ человек.

Во втором примере член клана с самым большим количеством «шестерок» ($$$1100$$$) вообще не успеет получить сообщение за $$$15$$$ минут, если не звонить ему напрямую, а человек с $$$1000$$$ «шестерок» не успеет получить сообщение, если звонить главе клана. Оптимальный ответ достигается, если звонить руководителю номер $$$2$$$: тогда сообщение получит он, двое его подчиненных ($$$3$$$ и $$$4$$$) и еще $$$100 + 50 + 1000$$$ их «шестерок», всего $$$1153$$$ человека.