چوب خط‌های نامتناهی


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

ابواسحاق که برای کدکاپ ۵ لحظه شماری می‌کرد، هر روزی که از برگزاری کدکاپ ۴ می‌گذشت روی تختهٔ خود یک چوب خط می‌کشید؛ اما چند روز پیش متوجه شد که کل تخته‌اش پر شده و باید آن را پاک کند. از آن‌جایی که تا کدکاپ چیزی باقی نمانده، از شما کمک می‌خواهد که تخته‌اش را برایش پاک کنید.

تختهٔ ابواسحاق به شکل یک جدول n×mn \times m کاملاً سیاه است و یک تخته پاک کن a×ba \times b در اختیار داریم. در هر مرحله می‌توانیم تخته پاک کن را یا به صورت افقی و یا به صورت عمودی (به طوری که اضلاع تخته پاک کن موازی با طول و عرض تخته باشد) ، بر روی تخته قرار دهیم و آن را به سمت دیگری بِکِشیم تا تمام خانه‌هایی که تخته پاک کن از روی آن عبور می‌کند، سفید شوند.

شما باید کمینه تعداد مراحل لازم را بگویید که بتوان تخته را کاملاً سفید کرد.

توجه کنید که در ابتدا تخته پاک کن بر روی تخته قرار ندارد.

ورودی🔗

ورودی شامل ۴ خط و در هر خط یک عدد است که به ترتیب نشانگر مقادیر nn، mm، aa و bb هستند. 1n,m1091 \le n, m \le 10^{9} 1a,bmin(n,m)1 \le a, b \le \min (n,m)

خروجی🔗

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

مثال🔗

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

3
3
1
3
Plain text

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

1
Plain text

برای این تست، می‌توانیم تخته پاک‌کن را به صورت افقی در بالای تخته قرار داده و آن را تا پایین تخته بِکِشیم. در این صورت کل تخته در ۱ مرحله پاک می‌شود. (مطابق شکل زیر)

خانه‌های آبی نشان‌ دهندهٔ تخته پاک کن هستند که در جدول قرار گرفته‌اند.

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

2
2
1
1
Plain text

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

2
Plain text

مطابق شکل زیر در دو مرحله می‌توان تخته را پاک کرد: توضیح تصویر