در کشوری n رودخانه وجود دارد. برای تامین برق این کشور، روی برخی از این رودخانهها سد احداث میکنیم. هزینه احداث سد روی رودخانهی i ام برابر bi است. بر روی هر سد میتوان به تعداد دلخواهی توربین نصب کرد. هزینهی نصب هر توربین در سد رودخانهی i ام برابر ci و توان خروجی آن برابر pi است. میخواهیم با صرف کمترین هزینه، مجموعا توان خروجی دقیقا معادل P داشته باشیم.
در سطر اول فایل ورودی ابتدا n و سپس P آمده است. در n سطر بعد، در هر سطر سه عدد bi و ci و سپس pi آمده است. فرض کنید تمامی اعداد ورودی مثبت هستند و در Integer جا میشوند. همچنین داریم: P≤15000 و نیز n≤500.
در فایل خروجی کمترین هزینه لازم را بنویسید.