+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در سال‌های اخیر تولید کننده‌های CPU، در تلاش بوده‌اند تا پردازنده‌هایی با تعداد هسته‌های پردازشی بیشتری تولید کنند. گاهی اوقات استفاده از چندین هسته برای پردازش‌های حجیم برای برنامه‌نویس‌ها چالش برانگیز می‌شود. معمولا وقتی پردازشی حجیم به چند بخش شکسته می‌شود، هزینه‌ی محاسباتی جدیدی برای شکستن کار و جمع بندی نتایج پردازش به وجود می‌آید. برای مثال انتظار داریم پردازشی که بر روی یک هسته در ۱۰۰۰ میلی‌ثانیه انجام می‌شود، روی دو هسته در ۵۰۰ میلی‌ثانیه انجام شود در حالی که در واقعیت ۶۵۰ میلی‌ثانیه زمان صرف پردازش می‌شود. تیم شما می‌خواهد پردازشی حجیم انجام دهد. برای این پردازش $J$ واحد محاسبه نیاز است انجام شود. اگر از چندین هسته برای انجام پردازش استفاده کنیم، پردازش به صورت برابر بین هسته‌ها تقسیم می‌شود. برای مثال اگر ۱۰۰۰ واحد محاسبه را بین ۳ پردازنده تقسیم کنیم هر پردازنده باید دقیقا $1000/3$ واحد محاسبه انجام دهد. شما تعدادی سیستم در دسترس دارید تا محاسبه را بر روی آن‌ها انجام دهید. هر سیستم تعدادی هسته دارد و سرعت پردازش هسته‌های هر سیستم یکسان است. شما باید یکی از سیستم‌ها را برای پردازش خود انتخاب کنید و تصمیم بگیرید از چند هسته‌ی آن برای پردازش استفاده می‌کنید. سیستم‌ها از ۱ تا $N$ شماره گذاری شده‌اند. سیستم $i$ام $c_i$ هسته دارد و هر هسته‌ی آن می‌تواند در هر میلی‌ثانیه $s_i$ واحد محاسبه انجام دهد. به دلیل سربار پردازش موازی، $P$ واحد محاسبه به ازای هر هسته بعد از اولین هسته به حجم کلی محاسبات اضافه می‌شود. این ثابت برای تمام سیستم‌های شما یکسان است. شما باید کوچک ترین عدد مثبت $T$ را بیابید که پردازش را می‌تواند در $T$ میلی‌ثانیه با تعدادی از پردازنده‌های یکی از سیستم‌ها انجام داد. # ورودی در خط اول ورودی اعداد $N$، $J$ و $P$ با فاصله از هم آمده است. در $N$ خط بعدی به ازای هر پردازنده اعداد $s_i$ و $c_i$ با فاصله از هم آمده است. $$1 \le N \le 50$$ $$1 \le J \le 10^9$$ $$0 \le P \le 10^6$$ $$1 \le s_i \le 10^6$$ $$1 \le c_i \le 10^3$$ # خروجی در تنها خط خروجی عدد $T$ را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 2000 5 40 2 20 4 ``` ## خروجی نمونه ۱ ``` 30 ``` توان پردازشی دو سیستم یکسان است ولی به دلیل سربار پردازش موازی از دو پردازنده‌ی سیستم اول استفاده می‌کنیم. ## ورودی نمونه ۲ ``` 2 2000 5 10 2 20 4 ``` ## خروجی نمونه ۲ ``` 40 ``` ## ورودی نمونه ۳ ``` 1 1000 0 10 3 ``` ## خروجی نمونه ۳ ``` 34 ``` ## ورودی نمونه ۴ ``` 3 10000 5 39 8 37 16 44 6 ``` ## خروجی نمونه ۴ ``` 63 ``` مشخصات پردازنده‌های امروزی تقریبا اینگونه است.