ركّب 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$. تضمن الاستراتيجية، مهما كان موضع البداية، ألا تزيد المسافة في الظلام عن المضيئة بأكثر من وحدتين.

مؤلف المسألة: Brian Dean