بعد أن أتعبته دراسة الخوارزميات المستمرة قليلًا، فكر 경근 أن الراحة في عالم آخر لبضعة أيام ستكون أمرًا جيدًا. وذات يوم أخبره 상수 بمكان باب يؤدي إلى عالم آخر، فذهب إليه. كان الباب مغلقًا وعليه قفل كبير ذو أقراص يمكن فتحه به.

يتكون القفل من $M$ قرص مرتبة رأسيًا. لكل قرص $R$ خانة، ويمكن تدويره يسارًا أو يمينًا بمقدار عدد صحيح من الخانات. قد تحتوي الخانة على نقطة وقد لا تحتوي. في كل قرص نقطة واحدة على الأقل. ينفتح الباب إذا دُوّرت الأقراص بحيث تحتوي جميع خانات عمود رأسي واحد في موضع ما على نقاط. تدور الأقراص بصورة مستقلة. ولأنها ثقيلة جدًا ويصعب تدويرها، نريد تقليل مجموع أعداد الخانات التي تدور خلالها.

يبين الشكل أعلاه مثالًا. إحدى الطرق المثلى هي تدوير القرص الأول من الأعلى خانة واحدة يسارًا، والثاني خانتين يسارًا، والثالث خانة واحدة يمينًا، وترك الرابع دون تدوير، بمجموع 4 خانات.

اكتب برنامجًا يتلقى أحجام الأقراص ومواضع النقاط ويحدد كيفية فتح الباب بأقل مجموع دوران. يُعطى موضع النقطة بزوج من رقم القرص ورقم الخانة. رقم القرص العلوي 0، وتزداد الأرقام بمقدار 1 نزولًا، فيكون رقم السفلي $M-1$. لترقيم الخانات، تُختار خانات أي موضع مشترك (عمود رأسي واحد) لتكون الخانة 0. تزداد الأرقام بمقدار 1 إلى اليمين، وتقع الخانة $R-1$ يسار الخانة 0. لا تتطابق إحداثيات نقطتين معطاتين.

long long findMinClicks( int M, int R, vector< pair<int, int> > P )

$M$ هو عدد الأقراص، و$R$ عدد الخانات في كل قرص. $P$ مصفوفة من $N$ زوجًا من قيم int. العدد الأول في كل زوج هو رقم القرص والثاني رقم الخانة. لا تتكرر الإحداثيات. يجب أن تعيد findMinClicks() أقل مجموع لأعداد الخانات التي يجب تدوير الأقراص خلالها لفتح الباب.

تفاصيل التنفيذ

يجب تقديم ملف واحد بالضبط اسمه dial.cpp، وأن ينفذ الدالة التالية.

long long findMinClicks( int M, int R, vector< pair<int, int> > P )

يجب أن تعمل الدالة كما وُصف أعلاه. يمكن إنشاء دوال أخرى واستخدامها داخليًا. لا يجوز للكود المقدم إجراء إدخال/إخراج أو الوصول إلى ملفات أخرى.

مثال برنامج التقييم

يقرأ برنامج التقييم المرفق الإدخال بالتنسيق التالي.

• السطر 1: الأعداد الصحيحة $N$ و$M$ و$R$.
• الأسطر من 2 إلى $N+1$: العددان الصحيحان $D_i$ و$C_i$.

هنا $(D_i,C_i)$ هما إحداثيا النقطة $i$. يطبع برنامج التقييم في سطر واحد القيمة التي تعيدها دالتك findMinClicks().

القيود

• $1\le R\le10^9$, $1\le N\le\min(MR,500\,000)$, $1\le M\le N$.

المهام الفرعية

المهمة الفرعية 1 (10 نقاط)

• $1\le N\le5\,000$, $1\le R\le5\,000$.

المهمة الفرعية 2 (15 نقاط)

• $1\le M\le5\,000$, $1\le R\le5\,000$.

المهمة الفرعية 3 (16 نقاط)

• $1\le N\le5\,000$.

المهمة الفرعية 4 (109 نقاط)

لا توجد قيود إضافية.

أمثلة

الإدخال 1

7 4 20
1 3
0 2
2 6
3 8
3 1
2 0
1 8

يُعرض أدناه مثال لتنفيذ الكود على الإدخال السابق.