Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Convex Countour

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given an strictly convex polygon with *n* vertices. It is guaranteed that no three points are collinear. You would like to take a maximum non intersecting path on the polygon vertices that visits each point at most once.

More specifically your path can be represented as some sequence of distinct polygon vertices. Your path is the straight line segments between adjacent vertices in order. These segments are not allowed to touch or intersect each other except at the vertices in your sequence.

Given the polygon, print the maximum length non-intersecting path that visits each point at most once.

Input

The first line of input will contain a single integer *n* (2 ≤ *n* ≤ 2 500), the number of points.

The next *n* lines will contain two integers *x*_{i}, *y*_{i} (|*x*_{i}|, |*y*_{i}| ≤ 10^{9}), denoting the coordinates of the *i*-th vertex.

It is guaranteed that these points are listed in clockwise order.

Output

Print a single floating point number, representing the longest non-intersecting path that visits the vertices at most once.

Your answer will be accepted if it has absolute or relative error at most 10^{ - 9}. More specifically, if your answer is *a* and the jury answer is *b*, your answer will be accepted if .

Example

Input

4

0 0

0 1

1 1

1 0

Output

3.4142135624

Note

One optimal path is to visit points 0,1,3,2 in order.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/14/2018 14:30:26 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|