Ural Dövlət Universitetinin prezidenti 80 illik yubiley gecəsini təşkil etmək qərarına gəlir. Universitet işçilərin iyerarxik strukturuna malikdir, yəni idarəetmə struktru kökündə prezident olan ağac formasındadır. İşçilər \textbf{1}-dən \textbf{N}-ə qədər intervalında tam ədədlərlə nömrələnmişdir. Kadrlar şöbəsi hər bir işçini xoşbəxtlik reytinqinə görə sıralamışdır. Yubiley gecəsinin hər bir işçi üçün şən keçməsi üçün prezident istəmir ki, işçi və onun müdiri birlikdə iştirak etsinlər. Sizin vəzifəniz, maksimal xoşbəxtlik reytinqinə görə qonaq siyahısını tərtib etməkdən ibarətdir. \InputFile Giriş verilənlərinin birinci sətrində \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{6000}) ədədi verilir. Hər bir altardıcıllığın \textbf{N} sətri işçilərin xoşbəxtlik reytinqini ehtiva edir. Xoşbəxtlik reytinqi \textbf{--128}-dən \textbf{127}-ə qədər intervalında hər hansı bir tam ədəddir. Bundan sonra idarəetmə ağacı verilir. Ağacın hər bir sətri aşağıdakı formatdadır: <\textbf{L}> <\textbf{K}> Bu \textbf{K} işçisinin \textbf{L} işçisinin müdiri olduğu bildirilir. Giriş \textbf{0} \textbf{0} sətri ilə tamamlanır və bu qiymətlər emal olunmur. \OutputFile Çıxışda qonaqların maksimal ümumi reytinqi verilməlidir.