תיאור הבעיה

בסוף השנה שעברה שכח סנטה קלאוס לתת מתנות חג מולד לילדי כפר 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$.