В одной Большой Софтверной Компании работает n человек, пронумерованных от 1 до n. Директору компании присвоен номер 1. У каждого сотрудника компании кроме директора есть ровно один непосредственный начальник. У директора, разумеется, начальника нет.

Будем называть человека a подчинённым другого человека b, если либо b — непосредственный начальник a, либо непосредственный начальник a подчинён человеку b. В частности, директору подчинены все остальные работники компании.

Для решения Важной Рабочей Задачи требуется сформировать рабочую группу. Каждый человек обладает некоторой эффективностью, выраженной целым положительным числом a_i, где i — номер человека. Эффективность рабочей группы определяется как суммарная эффективность всех людей, входящих в неё.

Работники Большой Софтверной Компании одержимы новыми модными способами организации рабочего процесса. Сейчас на пике популярности парное программирование, поэтому рабочая группа должна быть сформирована с соблюдением следующего условия. Каждый человек, входящий в рабочую группу, должен иметь возможность в процессе решения задачи разбить всех своих подчинённых, также попавших в рабочую группу, на пары. Иными словами, для каждого из членов рабочей группы количество подчинённых ему людей внутри рабочей группы должно быть чётным.

Требуется определить максимальную возможную эффективность рабочей группы, образованной с соблюдением указанного условия. В рабочую группу может войти любой человек, в том числе директор компании.