+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امین وارد یک آب‌میوه فروشی می‌شود. معده امین $V$ لیتر ظرفیت آب‌میوه دارد! در این آب‌میوه فروشی $n$ نوع آب‌میوه وجود دارد. انواع آب‌میوه را با اعداد $1$ تا $n$ شماره‌گذاری می‌کنیم. از آب‌میوه‌ی نوع $i$ام ($1 \leq i \leq n$) به اندازه‌ی $v_i$ لیتر در مخزن آن وجود دارد. امین می‌داند که اگر همه‌ی ظرف آب‌میوه‌ی موجود در مخزن $i$ام را بنوشد، به اندازه‌ی $h_i$ خوشحال می‌شود. همچنین اگر هر کسری از این ظرف را بخورد به همان نسبت خوشحالی بدست می‌آورد. (برای مثال اگر $\frac{1}{3} v_i$ لیتر بنوشد به‌اندازه‌ی $\frac{1}{3} h_i$ خوشحالی بدست می‌آورد.) حال امین می‌خواهد از هر نوع آب‌میوه مقداری بنوشد. (این مقدار می‌تواند هر عدد حقیقی نامنفی باشد!) به طوری که مجموع خوشحالی او بیشینه باشد. از شما می‌خواهیم برنامه‌ای بنویسید که این مقدار بیشینه را محاسبه و چاپ کند. # ورودی در سطر اول ورودی، عدد صحیح و مثبت $n$ و $V$ داده می‌شود. $$1 \leq n \leq 100 \, 000$$ $$1 \leq V \leq 10^9 $$ در $n$ سطر بعدی، در هر سطر، دو عدد $h_i$ و $v_i$ که با یک فاصله از هم جدا شده‌اند. $$1 \leq h_i, v_i \leq 10^9$$ # خروجی در تنها سطر خروجی، حداکثر مجموع خوشحالی که امین می‌تواند بدست بیاورد را چاپ کنید. **خروجی برنامه را با دقت دقیقاً یک رقم بعد از اعشار چاپ کنید.** # مثال‌ها ## ورودی نمونه ۱ ``` 3 400 100 200 150 140 100 300 ``` ## خروجی نمونه ۱ ``` 270.0 ``` ## ورودی نمونه ۲ ``` 1 10 500 30 ``` ## خروجی نمونه ۲ ``` 166.7 ``` <details class="blue"> <summary> **راهنمایی اول** </summary> ---------- ابتدا مسئله را برای حالت $n = 2$ حل کنید. </details> <details class="blue"> <summary> **راهنمایی دوم** </summary> ---------- اکنون که می‌توانید تصمیم بگیرد بین دو آبمیوه کدامیک الویت دارد. سعی کنید با همین روش همه‌ی آبمیوه‌ها را مرتب کنید. </details> <details class="blue"> <summary> **راهنمایی سوم** </summary> ---------- برای اینکه این مرتب‌سازی سریع باشد، سعی کنید از روش‌های مرتب‌سازی مقایسه‌ای مثل *merge sort* یا *quick sort* استفاده کنید تا به‌اندازه‌ی کافی راه‌حل شما سریع باشد. </details>

حل سؤال در بانک سؤالات