PROGRAMING PROBLEMS

Бяцхан хэмээх сууринд N оршин суугчтай. Уг суурины оршин суугч бүр өөр нэг оршин суугчаас тодорхой хэмжээний мөнгө зээлсэн байдаг. Одоо бүх өрийг төлөх цаг нь нэгэнт болсон боловч оршин суугчид мөнгөө бүгдийг нь зарцуулсан учраас хүндрэл гараад байгаа. Бяцхан суурины цагдаа энэ асуудлыг шийдэхээр шийджээ.

Бяцхан суурины захиргаа цөөн хэдэн оршин суугчид мөнгө өгөх ба тэд түүгээр өрөө төлөх боломжтой болно. Зарим оршин суугч мөнгөтэй болсноор өрөө төлөх гинжин үйлдэл эхэлнэ. Тухайлбал, А хүн захиргаанаас мөнгө авсан гэе. Тэгвэл А нь энэ мөнгийг В хүнд өрөө төлнө. Үүний дараа В нь авсан мөнгөөрөө C хүнд өрөө төлнө. Хэрэв өрөө төлөхөд хангалттай мөнгө байхгүй бол мөнгө зээлүүлсэн хүн хангалттай хугацаанд хүлээдэг. Хэрэв хангалттай мөнгөтэй болбол өрөө төлсний дараа үлдсэн мөнгөө хадгалдаг.

Жишээлбэл, хэрэв Бяцхан сууринд хоёр хүн амьдардаг ба тэд бие биедээ 1000 төгрөгийн өртэй бол суурины захиргаа тэдний нэгэнд нь 1000 төгрөг өгснөөр тэд өрөө төлж чадна.

Даалгавар: Суурины оршин суугчдын заримд нь захиргаанаас өгвөл зохих дээрх гинжин үйл явцаар бүх өрийг төлөгдөх хамгийн бага мөнгөний хэмжээг олно уу.

Оролт:

Оролтын эхний мөрөнд Бяцхан суурины оршин суугчдын тоо N (2 ≤ N ≤ 200 000) байна. Оршин суугчдыг 1-ээс N хүртэл дугаарладаг.

Дараах N мөрөнд хоосон зайгаар тусгаарлагдсан хоёр бүхэл тоо байна. Энэ нь i мөрийн эхний тоо Ai нь i дугаартай хүн (1 ≤ Ai ≤ N, Ai ≠ i)-ий мөнгө зээлсэн (өртэй) хүний ​​дугаарыг илэрхийлнэ. Хоёр дахь тоо Bi нь өрийн хэмжээг (1 ≤ Bi ≤ 10000) илэрхийлнэ.

Гаралт:

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

Жишээ: