Дано подвешенное дерево из $$$n$$$ вершин, корнем дерева является вершина $$$1$$$. Каждая вершина имеет некоторую неотрицательную цену. Листом дерева называется вершина, не являющаяся корнем, степень которой равна $$$1$$$.

Аркадий и Василий играют в странную игру на этом дереве. Игра состоит из трех этапов. На первом этапе Аркадий покупает некоторое непустое подмножество вершин дерева. На втором этапе Василий расставляет в листьях дерева некоторые целые числа. На третьем этапе Аркадий может несколько (возможно, ни одного) раз выполнить следующую операцию: выбрать некоторую купленную на первом этапе вершину $$$v$$$ и некоторое целое число $$$x$$$, а затем прибавить ко всем числам, расставленным в листьях поддерева вершины $$$v$$$, число $$$x$$$. Число $$$x$$$ может быть положительным, отрицательным или нулем.

Лист $$$a$$$ находится в поддереве вершины $$$b$$$, если простой путь от $$$a$$$ до корня проходит через $$$b$$$.

Задача Аркадия — сделать так, чтобы числа во всех листьях оказались равными нулю. Какую минимальную сумму $$$s$$$ он должен заплатить на первом этапе, чтобы гарантировать себе победу независимо от того, как Василий расставит числа на втором этапе? Кроме этого, найдите все такие вершины, что существует оптимальный (то есть со стоимостью $$$s$$$) набор вершин, включающий заданную, купив который Аркадий может гарантировать себе победу.