Во една голема фирма владее хиерархија на претпоставени во облик на дрво. Директорот е корен на тоа дрво, а секој друг работник има единствен непосреден шеф. Освен тоа, секој работник има официјален рејтинг (позитивен цел број) кој што ја одразува важноста на тој работник. Во фирмата се спрема свечен прием и директорот на фирмата е во дилема кои работници да ги повика. Директорот сака да постигне две цели. Никој да не се чувствува непријатно, се поканува или работникот или неговиот непосреден шеф (или никој), но никако двајцата. Освен тоа, газдата сака збирот на рејтингот на присутните работници да биде максимален. За секој од N -те работници нумерирани од 0 до N-1 даден е реден број Рu на непосредниот шеф (за директорот е дадена 0) и рејтинг Tu на тој работник. Да се направи оптимален избор на работниците кои ќе бидат повикани на приемот.

Влез

Во првата линија има еден цел број (N, N<5000) кој го означува вкупниот број на работиници во фирмата. Во втората линија е даден рејтингот на директорот. Редниот број на директорот е 0. Во наредните N-1 линии се дадени по два цели броја. Првиот го означува рејтингот на вработениот додека вториот редниот број на неговиот претпоставен. Редниот број на работникот соодвествува со бројот на линијата во која се наоѓа не сметајќи ја првата.

Излез

Во една линија се печати цел број и тоа максималниот рејтинг што може да се постигне на забавата ако се исполнети условите.

Ограничувања

Временско ограничување: 200 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
6
5
4 0
3 0
1 1
1 2
1 2

излез
8

влез
5
5
4 0
4 0
1 1
1 2

излез
8

влез
8
7
5 0
6 0
3 0
1 1
1 2
2 3
2 3

излез
15

Во првиот тест пример за присуство на свечениот прием се избрани директорот и работниците 3, 4 и 5. Во вториот тест пример се избрани се избрани работниците 1 и 2. Во третиот тест пример се избрани 1, 2, 6 и 7.

Теорија

(15) Напишете го псевдокогот на решението на проблемот
(10) Покажи како работи твојот алгоритам на двата примери
(10) Која е сложеноста на алгоритамот?