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

---

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

در فرایند ارسال مرسوله‌ها از مرکز پردازش به مرکز توزیع به هر راننده تعدادی مرسوله واگذار می‌شود که وظیفه‌ی تحویل این مرسوله‌ها را دارد. هر مرسوله وزن مشخصی دارد و باید به مرکز توزیع مشخصی فرستاده شود. این دو مقدار را با متغیر های $\mathrm {weight}$ و $\mathrm{delivery Center}$ مشخص می‌کنیم.

وسایل نقلیه راننده‌ها دو محدودیت حداکثر تعداد مرسوله قابل حمل و حداکثر وزن قابل حمل را دارد. این دو محدودیت را با متغیر‌های $\mathrm{max Packages}$ و $\mathrm{max Weight}$ مشخص می‌کنیم.

مرسوله‌ها به تریتب تاریخ تحویل به مشتری، به راننده تحویل داده می‌شوند و راننده نیز باید به همان ترتیب بسته‌ها را به مراکز توزیع تحویل دهد. راننده نمی‌تواند ترتیب مرسوله‌ها را به هم زده و به ترتیب دلخواه مرسوله‌ها را تحویل دهد.

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

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

ورودی

در خط اول ۴ عدد صحیح $m$، $n$، $\mathrm{max Packages}$ و $\mathrm{maxWeight}$ داده می‌شود که به ترتیب نمایانگر تعداد مراکز توزیع، تعداد مرسوله‌ها، حداکثر ظرفیت تعدادی و حداکثر ظرفیت حجمی راننده است. $$1 \leq n, m \leq 10 \ 000$$ $$1 \leq max Packages \leq m$$ $$1 \leq max Weight \leq 100 \ 000$$

در $n$ خط بعدی دو عدد صحیح $\mathrm{delivery Center}$​ و $\mathrm{weight}$ داده می‌شود که به ترتیب نشان دهنده شماره مرکز توزیع و وزن مرسوله است.

$$ 1 \leq weight \leq max Weight$$ $$ 1 \leq delivery Center \leq m $$

خروجی

در خروجی حداقل تعداد سفر لازم برای رساندن تمامی مرسوله‌ها را چاپ کنید.

مثال

ورودی نمونه ۱

2 3 3 4
1 1
2 1
1 1

خروجی نمونه ۱

4

حداقل تعداد سفر‌های لازم به این گونه است که راننده تمامی مرسوله‌ها را برداشته و به مرکز توزیع اول می‌رود (سفر اول) و مرسوله اول را تحویل می‌دهد. سپس به مرکز توزیع دوم رفته (سفر دوم) و مرسوله دوم را تحویل می‌دهد. در انتها نیز به مرکز توزیع اول بازگشته (سفر سوم) و مرسوله سوم را تحویل داده و به مرکز توزیع باز می‌گردد (سفر چهارم).

ورودی نمونه ۲

3 5 3 6
1 2
3 3
3 1
3 1
2 4

خروجی نمونه ۲

6

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

ورودی نمونه ۳

3 6 6 7
1 4
1 2
2 1
2 1
3 2
3 4

خروجی نمونه ۳

6

حداقل تعداد سفر‌های لازم به این گونه است که راننده مرسوله اول و دوم را برمی‌دارد و به مرکز توزیع شماره ۱ می‌رود و پس از تحویل مرسوله‌ها به مرکز پردازش باز می‌گردد (۲ سفر). سپس مرسوله‌های سوم و چهارم را برمی‌دارد و به مرکز توزیع شماره ۲ می‌رود و پس از تحویل مرسوله به مرکز پردازش باز می گردد (۲ سفر). در نهایت مرسوله پنجم و ششم را برمی‌دارد و به مرکز توزیع شماره ۳ رفته و پس از تحویل مرسوله‌ها به مرکز پردازش باز می‌گردد (۲ سفر).