Tắt đèn

Bessie ở trong một chuồng bò hình đa giác đơn giản với $N$ đỉnh (liệt kê theo chiều kim đồng hồ). Cửa ra ở đỉnh $1$. Các cạnh luôn song song với trục tọa độ (đa giác vuông góc).

Khi đèn tắt, Bessie ở tại một đỉnh nào đó (không biết đỉnh nào). Cô đi theo chiều kim đồng hồ dọc chu vi. Tại mỗi đỉnh, cô cảm nhận được góc trong (90° hoặc 270°), và độ dài cạnh cô vừa đi qua. Khi chuỗi quan sát chỉ khớp duy nhất một vị trí, cô biết mình ở đâu và chọn hướng ngắn nhất đến đỉnh $1$.

Hãy tìm khoảng cách dư tối đa (so với khi biết vị trí từ đầu) trong trường hợp xấu nhất.

Dữ liệu vào

• Dòng đầu: số nguyên $N$.
• $N$ dòng tiếp theo: tọa độ $(x_i,y_i)$ của các đỉnh theo chiều kim đồng hồ.

Dữ liệu ra

Một số nguyên duy nhất — khoảng cách dư tối đa.

Ràng buộc

• $4\le N\le 200$
• $-100000\le x_i,y_i\le 100000$

Ví dụ