• محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

بعد از به قدرت رسیدن کاکا در سرزمین غااززز، جدل و جدال بین کاکا و راک بیشتر و بیشتر شد...

کاکا از طریق جاسوس‌هایش خبردار شده که راک در پروژه‌ای جدید قصد دارد nn تانک متمایز طراحی کند.

همچنین میداند راک برای پروژه mm مهندس در اختیار دارد. پروسه طراحی تانک به این شکل است که هر مهندس در ساخت حداکثر یک تانک می‌تواند دخیل باشد (به دلایل فوق امنیتی)، و طراحی تانک ii ام به به اندازه tit_i تقسیم بر تعداد مهندس‌هایی که آن را طراحی می‌کنند زمان می‌برد.

یعنی اگر kk مهندس در طراحی تانک ii شرکت داشته باشند، طراحی این تانک tik\frac{t_i}{k} ساعت زمان می‌برد (این مقدار لزوماً صحیح نیست).

از آنجایی که منابع محدود است، طراحی تانک‌ها نمی‌تواند به صورت موازی انجام شود. یعنی در هر لحظه فقط یک تانک می‌تواند در حال ساخت باشد.

حال کاکا می‌خواهد بداند اگر راک به بهینه‌ترین روش عمل کند، پروسه ساخت تانک‌ها چند ساعت زمان می‌برد. دقت کنید پاسخ لزوماً عددی صحیح نیست و شما باید گرد شده عدد پاسخ را به عنوان جواب خروجی دهید.

ورودی

در خط اول n,mn, m به ترتیب تعداد تانک‌ها و تعداد مهندس‌ها داده می‌شود.

در nn خط بعد tit_i زمان ساخت تانک ii ام داده می‌شود.

ti,m1012t_i, m \le 10 ^ {12}n105 n \le 10 ^ {5} nmn \le m

خروجی

نزدیک‌ترین عدد صحیح به کمینه زمان ساخت تانک‌ها را خروجی دهید.

زیرمسئله‌‌ها

زیرمسئه نمره محدودیت
۱ ۵ m200,n30m \le 200 , n \le 30
۲ ۵۵ m3106 m \le 3 * 10 ^ 6
۳ ۴۰ بدون محدودیت بیشتر

مثال

ورودی نمونه ۱

2 5
10
4
Plain text

خروجی نمونه ۱

5
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.