Все в том же городе, где люди гуляли по улице, завелись бандиты! Один из таких, одетый в черную маску, задался целью поймать как можно больше мирных граждан.
Город состоит из \(n\) площадей, которые соединяют \(n-1\) дорог так, что от каждой площади обычно можно добраться до другой ровно одним способом. Площадь под номером \(1\) является главной площадью города.
Во время воскресной прогулки дороги между площадями в городе были изменены на односторонние таким образом, что теперь можно добраться от главной площади до любой другой.
Бандит высадился из автомобиля на главной площади города в тот момент, когда на \(i\)-й площади было \(a_i\) горожан. Далее происходит следующий процесс. Сначала каждый мирный горожанин, находящийся на площади, из которой выходит хотя бы одна односторонняя дорога, выбирает одну из таких дорог и перемещается по ней. Затем бандит выбирает одну из дорог, выходящих из площади, на которой он сейчас находится, и перемещается по ней. После этого процесс повторяется до тех пор, пока бандит не окажется на площади, из которой не выходит ни одной дороги. Бандит ловит всех граждан, оказавшихся на этой площади.
Бандит хочет задержать как можно больше горожан, а горожане не хотят быть пойманными, то есть хотят минимизировать количество задержанных. При этом бандит и горожане знают о расположении горожан на всех площадях в любой момент времени, а все горожане действуют сообща. Если каждая из сторон действует оптимально, то сколько горожан задержит бандит?
Примечание
В первом примере горожане на площади \(1\) могут разделиться на две группы \(2 + 1\), тогда на второй и третьей площади окажется по \(3\) человека.
Во втором примере независимо от действий граждан бандит сможет поймать хотя бы \(4\) человека.