در کشوری $n$ رودخانه وجود دارد. برای تامین برق این کشور، روی برخی از این رودخانه‌ها سد احداث می‌کنیم. هزینه احداث سد روی رودخانه‌ی $i$ ام برابر $b_i$ است. بر روی هر سد می‌توان به تعداد دلخواهی توربین نصب کرد. هزینه‌ی نصب هر توربین در سد رودخانه‌ی $i$ ام برابر $c_i$ و توان خروجی آن برابر $p_i$ است. می‌خواهیم با صرف کم‌ترین هزینه، مجموعا توان خروجی دقیقا معادل $P$ داشته باشیم.

در سطر اول فایل ورودی ابتدا $n$ و سپس $P$ آمده است. در $n$ سطر بعد، در هر سطر سه عدد $b_i$ و $c_i$ و سپس $p_i$ آمده است. فرض کنید تمامی اعداد ورودی مثبت هستند و در $Integer$ جا می‌شوند. همچنین داریم: $P\leq 15000$ و نیز $n\leq 500$.

در فایل خروجی کم‌ترین هزینه لازم را بنویسید.

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