وصف المسألة

في نهاية العام الماضي، نسي سانتا كلوز تقديم هدايا عيد الميلاد لأطفال قرية JOI. لذلك، وكتعبير عن اعتذاره، قرر توصيل كعك الشوكولاتة إلى الأطفال. وبما أن موعد التوصيل هو غدًا، فعليه أن يضع خطة للتنقل في أقرب وقت.

تنقسم قرية JOI على شكل شبكة بواسطة $W$ من الطرق المستقيمة الممتدة من الشمال إلى الجنوب و$H$ من الطرق المستقيمة الممتدة من الشرق إلى الغرب. الطرق الـ $W$ الممتدة من الشمال إلى الجنوب مرقمة بالترتيب من الغرب بالأرقام $1, 2, \dots, W$، والطرق الـ $H$ الممتدة من الشرق إلى الغرب مرقمة بالترتيب من الجنوب بالأرقام $1, 2, \dots, H$. يُرمز للتقاطع الذي يلتقي فيه الطريق الشمالي الجنوبي رقم $x$ من الغرب مع الطريق الشرقي الغربي رقم $y$ من الجنوب بالرمز $(x, y)$. يوجد في قرية JOI عدد $N$ من المنازل، ويقع كل منها عند أحد التقاطعات. لا يمكن لسانتا كلوز التحرك إلا على طول الطرق. الزمن اللازم للانتقال بين أي تقاطعين متجاورين هو $1$.

نظرًا لوجود أطفال في جميع منازل قرية JOI، يجب على سانتا كلوز المرور بجميع منازل قرية JOI لتوصيل كعكة شوكولاتة واحدة ($1$) لكل منزل. ولأن الطيران في السماء مع حيوانات الرنة حاملًا كعك الشوكولاتة الثمين يُعد أمرًا محفوفًا ببعض المخاطر، قرر سانتا كلوز وحيوانات الرنة الهبوط عند أحد تقاطعات قرية JOI، على أن يسير سانتا كلوز من هناك على قدميه لتوصيل كعك الشوكولاتة. لا يسير سانتا كلوز حاملًا كعكتين ($2$) أو أكثر من الشوكولاتة في نفس الوقت؛ أي أنه في كل مرة يوصل فيها كعكة شوكولاتة إلى منزل واحد ($1$)، يعود إلى التقاطع الذي هبط فيه.

قرر سانتا كلوز اختيار خطة تنقل تجعل الزمن الكلي المستغرق منذ هبوطه في قرية JOI وحتى انتهائه من توصيل كعك الشوكولاتة إلى جميع المنازل أصغر ما يمكن. لاحظ أن الزمن المستغرق للعودة إلى تقاطع الهبوط بعد توصيل كعكة الشوكولاتة إلى المنزل الأخير لا يُحتسب ضمن الزمن المستغرق. كما لا يُؤخذ في الاعتبار أي شيء سوى الزمن اللازم للتنقل.

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

الإدخال

اقرأ الإدخال التالي من الإدخال القياسي:

• يحتوي السطر $1$ على العددين الصحيحين $W, H$ مفصولين بمسافة، ويمثلان عدد الطرق في كل اتجاه.
• يحتوي السطر $2$ على عدد صحيح $N$ يمثل عدد المنازل.
• تحتوي الأسطر الـ $N$ التالية على معلومات مواقع المنازل. يحتوي السطر $(i + 2)$ ($1 \le i \le N$) على العددين الصحيحين $X_i, Y_i$ مفصولين بمسافة، ويمثلان أن المنزل $i$ يقع عند التقاطع $(X_i, Y_i)$. هذه التقاطعات الـ $N$ كلها مختلفة عن بعضها البعض.

الإخراج

اطبع البيانات التالية إلى الإخراج القياسي:

• يجب أن يحتوي السطر $1$ على عدد صحيح واحد ($1$) يمثل القيمة الصغرى للزمن المستغرق.
• في السطر $2$، عندما يكون التقاطع الذي ينبغي الهبوط فيه لتقليل الزمن المستغرق إلى الحد الأدنى هو $(x, y)$، يجب كتابة العددين الصحيحين ($2$) $x, y$ بهذا الترتيب مفصولين بمسافة. إذا وجدت عدة تقاطعات مناسبة، فاختر أكثرها اتجاهًا نحو الغرب (أي صاحب أصغر قيمة لـ $x$)؛ وإذا لم يتحدد تقاطع واحد ($1$) بعد ذلك، فاختر من بينها أكثرها اتجاهًا نحو الجنوب (أي صاحب أصغر قيمة لـ $y$).

مثال

مثال 1

الإدخال

5 4
3
1 1
3 4
5 3

الإخراج

10
3 3

التوضيح

على سبيل المثال، يمكن تقليل الزمن المستغرق إلى الحد الأدنى باتباع خطة التنقل التالية:

• الهبوط عند التقاطع $(3, 3)$.
• توصيل كعكة شوكولاتة إلى المنزل الواقع عند التقاطع $(3, 4)$. الزمن المنقضي حتى هذه اللحظة هو $1$.
• العودة إلى التقاطع $(3, 3)$. الزمن المنقضي حتى هذه اللحظة هو $2$.
• توصيل كعكة شوكولاتة إلى المنزل الواقع عند التقاطع $(5, 3)$. الزمن المنقضي حتى هذه اللحظة هو $4$.
• العودة إلى التقاطع $(3, 3)$. الزمن المنقضي حتى هذه اللحظة هو $6$.
• توصيل كعكة شوكولاتة إلى المنزل الواقع عند التقاطع $(1, 1)$. الزمن المنقضي حتى هذه اللحظة هو $10$.

مثال 2

الإدخال

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

الإخراج

21
2 3

التوضيح

لاحظ أنه يُسمح بالهبوط في تقاطع يوجد فيه منزل.

القيود

• $1 \le W \le 1000000000 = 10^9$: عدد الطرق الممتدة في اتجاه الشمال-الجنوب.
• $1 \le H \le 1000000000 = 10^9$: عدد الطرق الممتدة في اتجاه الشرق-الغرب.
• $1 \le N \le 100000 = 10^5$: عدد المنازل.
• $1 \le X_i \le W$: رقم الطريق الممتد في اتجاه الشمال-الجنوب لموقع المنزل $i$.
• $1 \le Y_i \le H$: رقم الطريق الممتد في اتجاه الشرق-الغرب لموقع المنزل $i$.

لاحظ أنه في هذه المسألة قد لا يتسع نطاق الأعداد الصحيحة المستخدمة في $32$ بت.

معايير التقييم

• بالنسبة لبيانات الاختبار التي تمثل $40\%$ من الدرجة الكلية، يتحقق $N \le 1000$.
• بالنسبة لبيانات الاختبار التي تمثل $10\%$ من الدرجة الكلية، يتحقق $W \le 50, H \le 50, N \le 1000$.