====== رودخانه‌ها ======



در کشوری $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$.

===== خروجي =====


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


===== ورودي و خروجي نمونه =====

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|2 8 \\ 10 21 2 \\ 13 40 4| ‎93‎ |

</WRAP>

  * [[سوال ۱۸|سوال بعد]]
  * [[سوال ۱۶|سوال قبل]]