Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۰:عملی:سوال ۱۷

رودخانه‌ها

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

ورودي

در سطر اول فایل ورودی ابتدا n و سپس P آمده است. در n سطر بعد، در هر سطر سه عدد bi و ci و سپس pi آمده است. فرض کنید تمامی اعداد ورودی مثبت هستند و در Integer جا می‌شوند. همچنین داریم: P15000 و نیز n500.

خروجي

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

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

ورودي نمونه خروجي نمونه
2 8
10 21 2
13 40 4
‎93‎

ابزار صفحه