معین در شهر بازی در یک بازی تیراندازی شرکت کرده است و می‌خواهد بیشترین امتیاز را کسب کند. او باید به تعدادی ظرف شلیک کند. ساختار ظرف‌ها به صورت یک درخت ریشه‌دار است (ظرف‌ها به منزله‌ی رئوس درخت می‌باشند) که ریشه در پایین‌ترین ارتفاع قرار دارد و مسیر از ریشه به برگ‌ها از پایین به بالا می‌باشد. در هر راس(یعنی ظرف) در ابتدا مقداری آب وجود دارد. هر راس غیر ریشه پدری دارد که وقتی معین این ظرف را با تیر می‌زند، تمام آب این ظرف، به پدرش منتقل می‌شود، البته در صورتی که قبلا ظرف پدر را نزده باشد. مقدار امتیازی که معین به دست می‌آورد برابر با مقدار آبی است که نهایتاً در ظرف ریشه جمع می‌شود. او در هر مرحله می‌تواند یک ظرف را با تیر بزند، و هر موقع بخواهد می‌تواند شلیک کردن را قطع کند و برابر با مقدار آب موجود در ظرف ریشه، امتیاز خواهد داشت. دقت کنید که اگر در یک مرحله، به یک ظرف شلیک کند، دیگر هیچ راهی برای انتقال آب ظرف‌هایی که در زیر درخت آن راس قرار دارند به راس ریشه وجود نخواهد داشت. تعداد ظرف‌ها ‎$n$‎تا و مقدار آب اولیه‌ی موجود در ظرف ‎$i$‎ام عدد صحیح غیر منفی ‎$w_i$‎ می‌باشد. نکته‌ی مهم این است که اگر در یک مرحله، مقدار آبی که در یک ظرف جمع می‌شود، بیشتر از ظرفیت آن باشد، معین کلاً مسابقه را می‌بازد و هیچ امتیازی به دست نمی‌آورد. ظرفیت ظرف ‎$i$‎ام برابر با عدد طبیعی ‎$c_i$‎ می‌باشد.

شما باید برنامه‌ای بنویسید که با گرفتن اطلاعات مربوطه، بیش‌ترین امتیازی که معین می‌تواند کسب کند را به‌دست بیاورد‎.‎

• در سطر اول ورودی عدد طبیعی $(1 \leq n \leq 300)$ آمده است‎.
• در ‎$n$‎ سطر بعد، در هر سطر اطلاعات مربوط به یک ظرف آمده است؛ در سطر ‎$i+1$‎ام، اطلاعات ظرف ‎$i$‎ نوشته شده است، به این صورت که ابتدا شماره‌ی راس پدر آن، سپس به ترتیب دو عدد طبیعی $(1 \leq c_i \leq 300)$ و $(0 \leq w_i \leq 300)$‎ نوشته شده است.‎
• ظروف به ترتیب ورودی از ‎$1$‎ تا ‎$n$‎ شماره گذاری شده‌اند و ظرف شماره یک، ظرف ریشه است‎.‎
• به دلیل این که ظرف شماره ‎$1$‎ پدر ندارد، به جای شماره پدر آن در ورودی عدد ‎$-1$‎ آمده است.

خروجی تنها باید شامل یک عدد صحیح باشد که نشان‌دهنده‌ی بیش‌ترین امتیازی است که معین می تواند کسب کند.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل