لینک‌های مفید برای شرکت در مسابقه:

در طول مسابقه، می‌توانید سؤالات خود را از قسمت «سؤال بپرسید» مطرح کنید.

جعبه شکلات


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

استاد و kk شاگردش بـه مـغازه شکلات فـروشی سـر کوچه که nn جـعبه شکلات دارد می‌رونـد. جعبه شـکلات iiام aia_i شکلات دارد و cic_i تومان قیمت دارد. استاد و شاگردانش در صورتی حین خوردن یک جعبه شکلات دعوایشان نمی‌شود که ۲ شرط زیر برقرار باشد:

  1. شاگرد‌ها همه به تعداد برابر شکلات بخورند و استاد دقيقاً ۱ شکلات از شاگرد‌ها بيشتر.
  2. همه حداقل ۱ شکلات بخورند.

دقت کنید که شکلات‌ها بین افراد افراز می‌شود (یعنی همه‌ی شکلات‌ها پخش می‌شود و یک شکلات را ۲ نــفر نمی‌خورند). اسـتاد vv تومان پـول دارد و بـا پـولـش می‌خواهد بیشـتریـن تعداد جعبه شکلات را بخرد به طوری که حین خـوردن هیچ کدام از جعبه شکلات‌ها بـینشان دعوا نشود (دقت کنید، ابتدا یک جعبه شکلات را بین خود تقسیم می‌کنند و می‌خوردند و سپس جعبه بعدی را باز می‌کنند). حال استاد از شما می‌خواهد تا بگویید حداکثر چند جعبه شکلات می‌تواند بخرد.

ورودی🔗

در سطر اول به ترتيب سه عدد kk، vv و nn و در سطر بعدی nn عدد می‌آید که iiامين آن‌ها aia_i است و درسطر بعدی nn عدد می‌آید که iiامین آن‌ها cic_i است.

1n,k1000001 \leq n, k \leq 100000 1ci,ai,v1091 \leq c_i, a_i, v \leq 10^9

خروجی🔗

تعداد حداکثر جعبه شکلاتی که می‌توانند بخرند و با خوردنش بینشان دعوت نشود.

مثال‌🔗

ورودی نمونه ۱🔗

3 10 5
5 9 10 4 14
1 10 2 1 3
Plain text

خروجی نمونه ۱🔗

1
Plain text

جعبه‌های اول و دوم را می‌توان بخرد به طوری کـه حین خـوردن شکلات‌هایش بـینشان دعـوا نشود و با پولی که دارد از میان این ۲ حداکثر یکی را می‌تواند بخرد.

ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.