Farmer John התקין ברפת מכונת חליבה חדשה ומשוכללת, אך היא צורכת כל כך הרבה חשמל שלעיתים היא גורמת להפסקת חשמל! זה קורה לעיתים קרובות כל כך ש־Bessie שיננה את מפת הרפת כדי למצוא את היציאה ביתר קלות בחושך. היא סקרנית כיצד ההפסקות משפיעות על יציאה מהירה, למשל כמה יותר תצטרך ללכת בחושך.

הרפת היא מצולע פשוט (ללא חיתוך עצמי), שקודקודיו השלמים $(x_1, y_1) \ldots (x_n, y_n)$ נתונים עם כיוון השעון. הצלעות מתחלפות בין אופקיות (מקבילות לציר $x$) לאנכיות (לציר $y$); הראשונה יכולה להיות מכל סוג. היציאה ב־$(x_1, y_1)$. Bessie מתחילה ברפת בקודקוד $(x_i, y_i)$ עם $i > 1$. היא יכולה ללכת רק על ההיקף עם או נגד כיוון השעון, ורוצה מרחק מינימלי ליציאה. באור קל לבחור את הכיוון הקצר יותר מהמיקום הנוכחי ליציאה.

יום אחד האורות כבים, ו־Bessie נבהלת ושוכחת באיזה קודקוד היא. היא עדיין זוכרת את המפה המדויקת ויכולה לגלות את מיקומה בהליכה ובמישוש. בכל קודקוד, כולל ההתחלתי, היא חשה את הזווית הפנימית המדויקת ויודעת אם הוא היציאה. לאחר הליכה לאורך צלע שלמה היא יודעת את אורכה המדויק. האסטרטגיה היא ללכת עם כיוון השעון עד שחשה מספיק זוויות וצלעות כדי להסיק את הקודקוד הנוכחי. אז היא הולכת את המרחק הנותר המינימלי ליציאה, בהמשך עם כיוון השעון או בהיפוך הכיוון.

מצאו את הגידול המרבי במרחק ההליכה בחושך לעומת רפת מוארת, במקרה הגרוע ביותר מכל קודקודי ההתחלה האפשריים.

קלט

השורה הראשונה מכילה את $N$ ($4 \leq N \leq 200$). כל אחת מ־$N$ השורות הבאות מכילה שני שלמים עבור $(x_i, y_i)$ עם כיוון השעון. המספרים בטווח $-100,000 \ldots 100,000$.

פלט

הדפיסו את הגידול המרבי במרחק ממיקום ההתחלה הגרוע ביותר לפי האסטרטגיה המתוארת.

דוגמאות

קלט 1

4
0 0
0 10
1 10
1 0

פלט 1

2

הערה

בדוגמה Bessie חשה תחילה זווית של 90 מעלות, אך אינה מבדילה בין הקודקודים 2, 3 ו־4. אחרי הליכה לאורך צלע עם כיוון השעון היא מגיעה ליציאה או מזהה באופן יחיד את מיקומה לפי אורך הצלע. המרחקים הם:

מקודקוד 2: בחושך 12 יחידות (1 לקודקוד 3 ואז 11 ליציאה), ובאור רק 10. התוספת היא 2.

מקודקוד 3: 11 יחידות בשני המקרים.

מקודקוד 4: יחידה אחת בשני המקרים.

לכן ההפרש הגרוע ביותר הוא $12 - 10 = 2$. האסטרטגיה מבטיחה מכל התחלה לכל היותר 2 יחידות נוספות בחושך לעומת האור.

מחבר הבעיה: Brian Dean