«Съел бобра — спас дерево!» — именно под таким девизом пройдёт срочный слёт экологов в городе Бобруйске.

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

В середине 50-х годов прошлого века группа советских учёных смогла спрогнозировать ситуацию с бобрами и разработала секретную технологию по очистке территории под таинственным названием «Боброжуй-0xFF». Теперь судьба планеты лежит на хрупких плечах всего нескольких людей, отдавших свою жизнь науке.

Прототип уже готов, теперь нужно срочно проводить его испытания в полевых условиях.

Вам дано дерево, сплошь усеянное бобрами. Дерево состоит из n вершин, в i-ой вершине расположилось k_i бобров. Напомним, дерево — это связный неориентированный граф без циклов.

«Боброжуй-0xFF» работает по следующему принципу: находясь в некоторой вершине u, он может перейти к вершине v, если они соединены ребром, и съесть ровно одного бобра из тех, что находятся в вершине v. Переместиться в вершину v невозможно, если в ней не осталось бобров. «Боброжуй-0xFF» не может просто так стоять в какой-то вершине и есть там бобров. Он должен двигаться без остановок.

Почему «Боброжуй-0xFF» работает именно так? Потому что разработчики не предусмотрели место в нём для аккумулятора, а поедание бобров необходимо для перегона их массы в чистую энергию.

Гарантируется, что бобры будут находиться в шоке от происходящего, поэтому не смогут перемещаться по дереву. В свою очередь, «Боброжуй-0xFF» может перемещаться по каждой ветке в обоих направлениях сколько угодно раз, пока условия, описанные выше, выполняются.

Корень дерева находится в вершине s. Это значит, что «Боброжуй-0xFF» начинает свою миссию в вершине s и обязательно должен в неё же вернуться в конце испытания, потому что снимать его с большой высоты никто не намерен.

Определите максимальное количество бобров, которое сможет съесть «Боброжуй-0xFF», вернувшись при этом в стартовую вершину.