+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- استاد و $k$ شاگردش بـه مـغازه شکلات فـروشی سـر کوچه که $n$ جـعبه شکلات دارد می‌رونـد. جعبه شـکلات $i$ام $a_i$ شکلات دارد و $c_i$ تومان قیمت دارد. استاد و شاگردانش در صورتی حین خوردن یک جعبه شکلات دعوایشان نمی‌شود که ۲ شرط زیر برقرار باشد: 1. شاگرد‌ها همه به تعداد برابر شکلات بخورند و استاد دقيقاً ۱ شکلات از شاگرد‌ها بيشتر. 2. همه حداقل ۱ شکلات بخورند. دقت کنید که شکلات‌ها بین افراد افراز می‌شود (یعنی همه‌ی شکلات‌ها پخش می‌شود و یک شکلات را ۲ نــفر نمی‌خورند). اسـتاد $v$ تومان پـول دارد و بـا پـولـش می‌خواهد بیشـتریـن تعداد جعبه شکلات را بخرد به طوری که حین خـوردن هیچ کدام از جعبه شکلات‌ها بـینشان دعوا نشود (دقت کنید، ابتدا یک جعبه شکلات را بین خود تقسیم می‌کنند و می‌خوردند و سپس جعبه بعدی را باز می‌کنند). حال استاد از شما می‌خواهد تا بگویید حداکثر چند جعبه شکلات می‌تواند بخرد. # ورودی در سطر اول به ترتيب سه عدد $k$، $v$ و $n$ و در سطر بعدی $n$ عدد می‌آید که $i$امين آن‌ها $a_i$ است و درسطر بعدی $n$ عدد می‌آید که $i$امین آن‌ها $c_i$ است. $$1 \leq n, k \leq 100000$$ $$1 \leq c_i, a_i, v \leq 10^9$$ # خروجی تعداد حداکثر جعبه شکلاتی که می‌توانند بخرند و با خوردنش بینشان دعوت نشود. # مثال‌ ## ورودی نمونه ۱ ``` 3 10 5 5 9 10 4 14 1 10 2 1 3 ``` ## خروجی نمونه ۱ ``` 1 ``` جعبه‌های اول و دوم را می‌توان بخرد به طوری کـه حین خـوردن شکلات‌هایش بـینشان دعـوا نشود و با پولی که دارد از میان این ۲ حداکثر یکی را می‌تواند بخرد.