Masala F

Sardor katta bir kompaniyaning rahbari bo'lib, u sohadagi yetakchi kompaniya hisoblanadi. Kompaniyaning muvaffaqiyat siri — ichki boshqaruv tizimida. Kompaniyadagi har bir xodimga \(1\) dan \(N\) gacha bo'lgan alohida raqam berilgan bo'lib, har bir xodimning bevosita bo'limi boshlig'i ma'lum (1-raqamli xodim — bu Sardorning o'zi va uning hech qanday boshlig'i yo'q). Xodimlar o'rtasidagi munosabatlar ildizi 1-tugundan boshlanadigan daraxt tuzilmasini hosil qiladi.

Kompaniya xalqaro ko'rgazmaga taklif qilindi. Ko'rgazmada kompaniya ma'lum miqdordagi jamoalar (Sardor tomonidan belgilanadi) bilan qatnashadi, har bir jamoada ikkita xodim bo'ladi. Sardorga jamoalarning soni emas, ularning qiymati muhim. Shu sababli u quyidagi qoidani belgiladi: \(x\) va \(y\) xodimlar jamoani tashkil eta oladi, agar \(x\) — \(y\) ning bevosita rahbari bo'lsa, yoki ikkalasi ham bir xil rahbarga ega bo'lsa. Bunday jamoaning qiymati \(|x - y|\) ga teng. Shuningdek, Sardor (1-raqamli xodim) hech qanday jamoaga kirmaydi — u kompaniya menedjeri sifatida alohida turadi. Jamoalarning umumiy qiymati barcha jamoalar qiymatlarining yig'indisiga teng.

Har bir xodim faqat bitta jamoaga kirishi mumkin.

Shunday jamoalar tarkibini toping-ki, jamoalarning umumiy qiymati maksimal bo'lsin.

Birinchi qatorda butun son \(N\) — kompaniyadagi xodimlar soni.

Keyingi \(N-1\) ta qatorda xodimlar ierarxiyasi haqida ma'lumot beriladi: \(i\)-qatorda \(i\)-xodimning bevosita rahbarining raqami yozilgan.

\(1 \le N \le 1000\)

Ko'rgazmaga yuboriladigan jamoalarning maksimal umumiy qiymatini chop eting.