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