- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در شهر کدکاپآباد تنها یک خط مترو وجود دارد که هر روز تنها یک بار از ایستگاه ۱ شروع کرده و تا ایستگاه آخر میرود. \(n\) ساکن این شهر هر روز صبح برای رفتن به سر کار از این خط مترو استفاده میکنند.
شهروند \(i\)ام اول صبح میخواهد از ایستگاه \(s_i\) به ایستگاه \(e_i\) برود. قطار شهر کدکاپآباد بسیار قدیمی است و حداکثر \(L\) نفر میتوانند سوار آن شوند. هر فرد میتواند در ایستگاه \(s_i\) سوار قطار شود و در یکی از ایستگاههای ادامهی مسیر پیاده شود و باقی مسیر را پیاده برود.
اگر شهروند \(i\)ام در ایستگاه \(m_i\) از قطار پیاده شود باید \(\mid m_i-e_i \mid\) واحد پیاده برود. زمان پیاده شدن هر شهروند از قطار طوری تعیین کنید که مجموع میزان پیاده روی شهروندان کمینه شود. (توجه کنید که \(m_i\) میتواند برابر با \(s_i\) باشد. یعنی شما میتوانید یکی از شهروندان را اصلاً سوار قطار نکنید.)
ورودی
در سطر اول ورودی، دو عدد صحیح و مثبت \(n\) و \(L\) آمده است که \(n\) نشان دهندهی شهروندان شهر کدکاپآباد و \(L\) نشان دهندهی حداکثر تعداد مسافر سوار بر قطار است.
\[1 \leq n, L \leq 100 \, 000\]
در هر کدام از \(n\) سطر بعدی، در سطر \(i\)ام \(s_i\) و \(e_i\) آمده است که نشان دهندهی مبدا و مقصد شهروند \(i\) ام است. \[1 \leq s_i \lt e_i \leq 300 \, 000\]
خروجی
کمینهی مجموع خستگی شهروندان را چاپ کنید.
مثالها
ورودی نمونه ۱
2 1
1 2
2 3
خروجی نمونه ۱
0
توضیح نمونه ۱
- در ایستگاه ۱ مسافر ۱ را سوار میکند.
- در ایستگاه ۲ مسافر ۱ را پیاده میکند و مسافر ۲ را سوار میکند.
- در ایستگاه ۳ مسافر ۲ را پیاده میکند.
به این ترتیب هر دو مسافرها در مقصدی که میخواهند پیاده میشوند. پس مجموع خستگیها \(0 + 0 = 0\) میشود.
ورودی نمونه ۲
4 1
1 3
2 4
3 5
5 7
خروجی نمونه ۲
2
توضیح نمونه ۲
- در ایستگاه ۱ مسافر ۱ را سوار میکند.
- در ایستگاه ۳ مسافر ۱ را پیاده میکند و مسافر ۳ را سوار میکند.
- در ایستگاه ۵ مسافر ۳ را پیاده میکند و مسافر ۴ را سوار میکند.
- در ایستگاه ۷ مسافر ۴ را پیاده میکند.
به این ترتیب مسافرهای ۱، ۳ و ۴ در مقصدی که میخواهند پیاده میشوند ولی مسافر ۲ اصلاً سوار نشده و باید پیاده به مقصدش برود و بهاندازهی \(\mid 4 - 2 \mid = 2\) خسته میشود. پس مجموع خستگیها \(0 + 2 + 0 + 0 = 2\) میشود.
ورودی نمونه ۳
4 2
4 9
1 7
2 10
3 6
خروجی نمونه ۳
6
توضیح نمونه ۳
- در ایستگاه ۱ مسافر ۲ را سوار میکند.
- در ایستگاه ۲ مسافر ۳ را سوار میکند. (توجه کنید اینبار ۲ نفر ظرفیت دارد.)
- در ایستگاه ۴ مسافر ۲ را پیاده میکند و مسافر ۱ را سوار میکند.
- در ایستگاه ۹ مسافر ۱ را پیاده میکند.
- در ایستگاه ۱۰ مسافر ۳ را پیاده میکند.
به این ترتیب مسافرهای ۱ و ۳ در مقصدی که میخواهند پیاده میشوند ولی مسافر ۴ اصلاً سوار نشده و باید پیاده به مقصدش برود و بهاندازهی \(\mid 6 - 3 \mid = 3\) خسته میشود. همچنین مسافر ۲ در ایستگاه ۴ پیاده شده ولی میخواست به ایستگاه ۷ برود و بهاندازهی \(\mid 7 - 4 \mid = 3\) خسته میشود.
پس مجموع خستگیها \(0 + 3 + 0 + 3 = 6\) میشود.
ارسال پاسخ برای این سؤال