برای گرفتن ورودی از توابع ()raw_input یا ()input استفاده کنید.

تخریب سد


سد nn طبقه‌ای دیمونا، بزرگترین سد بنا شده در سرزمین‌های اشغالی است. می‌دانیم در پشت طبقه iiام این سد، WiW_i لیتر آب وجود دارد. هم‌چنین می‌دانیم طیقه iiام قادر به تحمل LiL_i لیتر آب است و اگر میزان آب پشت آن بیشتر از این حد شود، آن طبقه تخریب شده و تمام آب‌های موجود پشت آن به طبقه‌ای که بلافاصله پایین‌تر قرار دارد منتقل می‌شود.

گروه های مبارز فلسطینی قصد دارند پایین‌ترین طبقه این سد (طبقه nnام) را تخریب کنند. می‌دانیم تخریب طبقه iiام سد با مواد منفجره، PiP_i واحد هزینه دارد؛ از طرفی دوستان فلسطینی ما با محدودیت بودجه روبه‌رو هستند. شما برای کمک به گروه‌های مبارز فلسطینی به مناطق اشغالی اعزام شده‌اید. الگوریتمی (بهینه) ارائه دهید که حداقل هزینه ممکن برای تخریب پایین‌ترین طبقه سد را بیابد.

ورودی🔗

در خط اول، ورودی شامل (n)(n) تعداد طبقات این سد است.

در ادامه nn خط می‌آید که در هر خط ۳ عدد WiW_i ،LiL_i ‌و PiP_i داده خواهد شد.

خروجی🔗

در تنها سطر خروجی، حداقل هزینه برای تخریب پایین‌ترین طبقه این سد را چاپ کنید.

محدودیت‌ها🔗

  • n1.5×104n \leq 1.5 \times 10^4
  • 0Wi,Li,Pi1060 \leq W_i, L_i, P_i \leq 10^6

مثال🔗

ورودی نمونه

3
1000 1000 1
0 1000 2
2 10 100
Plain text

خروجی نمونه

3
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.