B. Тусгай баг

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нэгэн програм хангамжийн компани нь $1$-ээс $n$ хүртэл дугаарлагдсан $n$ ажилчинтай. Захирал $1$ дугаартай ба захирлаас бусад бүх ажилчид яг нэг шууд зааварлагчтай. Мэдээж захиралд хэн ч зааварлахгүй.

Хэрэв $b$ хүн $a$ хүний шууд зааварлагч эсвэл $a$ хүний шууд зааварлагч нь $b$ хүний харьяат бол $a$-г $b$ хүний харьяат гэж нэрлэнэ. Захирлын харьяанд бүх ажилчид багтана.

Нэгэн чухал зорилтийг биелүүлэхийн тулд ажилчдын дундаас нэгэн тусгай баг бүрдүүлэх хэрэгтэй болов. Хүн бүр $a_{i}$ гэсэн эерэг бүхэл тоогоор илэрхийлэгдэх ажлын бүтээмжтэй ($i$ нь тухайн хүний дугаарыг илтгэнэ). Тусгай багийн ажлын бүтээмж нь тухайн багийн бүх гишүүдийн нийт ажлын бүтээмжээр тодорхойлогддог.

Энэ компани нь pair programming буюу ажилчид хосоороо цуг сууж програм бичиж ажиллах арга барилыг эрхэмлэдэг учраас тусгай багийн аль гишүүний харьяаных нь хүмүүсийн тоо тэгш тоотой байхаар хуваарилахыг хүсэв.

Чиний зорилго өгөгдсөн нөхцлийн дагуу хамгийн их ажлын бүтээмжтэй тусгай багийг сонгох юм. Захирлыг оруулаад ямар ч хүн тусгай багт орж болно.

Оролт

Хамгийн эхний мөрөнд компанийн нийт ажилчдын тоо болох $n$ ($1 ≤ n ≤ 2 \cdot 10^{5}$) бүхэл тоог оруулна.

Дараачийн $n$ мөрөнд компанийн ажилчдын тухай оруулна. $i$ дэх мөрөнд харгалзан $i$ дэх дугаарын хүний шууд зааварлагчийн дугаар ба ажлынх нь бүтээмжийг илэрхийлсэн $p_{i}, a_{i}$($1 ≤ a_{i} ≤ 10^{5}$) бүхэл тоонуудыг оруулна. Захирлын хувьд $p_{1}=-1$ ба бусад ажилчдын хувьд $1 ≤ p_{i} < i$ гэсэн нөхцлийг хангана.

Гаралт

Тусгай багийн боломжит хамгийн их ажлын бүтээмжийг илэрхийлсэн тоог хэвлэ.

Орчуулсан: Э.Оргил-Эрдэнэ

Жишээ тэстүүд

Оролт
7
-1 3
1 2
1 1
1 4
4 5
4 3
5 2
Гаралт
17

Тэмдэглэл

Эхний жишээнд хамгийн үр бүтээлтэй багийг үүсгэхийн тулд $1, 2, 4, 5, 6$ дугаартай ажилчдыг сонгосон байна.

Сэтгэгдлүүдийг ачааллаж байна...