Ректор Уральского Державного Університету вирішив організувати ювілейний вечір до \textbf{80}-річчя заснування університету. Університет має ієрархічну структуру працівників, тобто відношення керівників та підлеглих утворюють дерево, у корені якого знаходиться ректор. Співробітників пронумеровано цілими числами у діапазоні від \textbf{1} до \textbf{N}. Відділ кадрів надав інформацію про святковий настрій кожного співробітника. Для того, щоб зробити ювілейний вечір приємним для усіх його участників, ректор не хоче, щоб у ньому одночасно брали участь співробітник та його безпосередній начальник. Ваша задача скласти для ректора список гостей з максимальним святковим настроєм. \InputFile Перший рядок містить кількість співробітників університету \textbf{N} ( \textbf{1} ≤ \textbf{N} ≤ \textbf{6000}). Кожен з наступних \textbf{N} рядків містить святковий настрій відповідного працівника. Святковий настрій є цілим числом у межах від \textbf{--128} до \textbf{127}. Після цього задано дерево відношень працівників та їх керівників. Кожен рядок опису дерева має вигляд: \textbf{L K} що означає, що \textbf{K}-ий працівник є безпосереднім керівником \textbf{L}-го працівника. Вхідні дані завершуються рядком, який містить два нулі (цей рядок не опрацьовується): \textbf{0 0} \OutputFile Вихід повинен містити максимальний сумарний святковий настрій гостей.