سد $n$ طبقه‌ای دیمونا، بزرگترین سد بنا شده در سرزمین‌های اشغالی است. می‌دانیم در پشت طبقه $i$ام این سد، $W_i$ لیتر آب وجود دارد. هم‌چنین می‌دانیم طیقه $i$ام قادر به تحمل $L_i$ لیتر آب است و اگر میزان آب پشت آن بیشتر از این حد شود، آن طبقه تخریب شده و تمام آب‌های موجود پشت آن به طبقه‌ای که بلافاصله پایین‌تر قرار دارد منتقل می‌شود. گروه های مبارز فلسطینی قصد دارند پایین‌ترین طبقه این سد (طبقه $n$ام) را تخریب کنند. می‌دانیم تخریب طبقه $i$ام سد با مواد منفجره، $P_i$ واحد هزینه دارد؛ از طرفی دوستان فلسطینی ما با محدودیت بودجه روبه‌رو هستند. شما برای کمک به گروه‌های مبارز فلسطینی به مناطق اشغالی اعزام شده‌اید. الگوریتمی (بهینه) ارائه دهید که حداقل هزینه ممکن برای تخریب پایین‌ترین طبقه سد را بیابد. ## ورودی در خط اول، ورودی شامل $(n)$ تعداد طبقات این سد است. در ادامه $n$ خط می‌آید که در هر خط ۳ عدد $W_i$ ،$L_i$ ‌و $P_i$ داده خواهد شد. ## خروجی در تنها سطر خروجی، حداقل هزینه برای تخریب پایین‌ترین طبقه این سد را چاپ کنید. ## محدودیت‌ها + $n \leq 1.5 \times 10^4$ + $0 \leq W_i, L_i, P_i \leq 10^6$ ## مثال ورودی نمونه ``` 3 1000 1000 1 0 1000 2 2 10 100 ``` خروجی نمونه ``` 3 ```