Signal 1

Interview

Time limit1.5sMemory limit128 MB

Summary

Choose a subset of points with distinct x-coordinates; maximize the total Euclidean length of the polyline joining them in increasing x order.

Level: Medium5 of 10
Topics: Dynamic programming, Sorting, Geometry, Math
Solved: No attempts yet

Problem

There are $N$ signals on the coordinate plane. Signal $i$ sits at $(x_i, y_i)$ , and no two signals share a position.

A communication system is built by choosing some of the signals and joining them with segments in order of increasing $x$ coordinate. The chosen signals must have pairwise different $x$ coordinates. The length of the system is the sum of the Euclidean distances between consecutive signals, and a system built from a single signal has length 0.

Build the communication system of greatest length so that a signal reaches as far as possible, then report that length.

Input

The first line contains the number of signals $N$ ( $1 \le N \le 1000$ ).

Each of the next $N$ lines contains the coordinates $x_i$ and $y_i$ of one signal, separated by a space ( $-10^4 \le x_i, y_i \le 10^4$ , and $x_i$ and $y_i$ are integers).

No coordinate pair is given twice.

Output

Print the length of the longest communication system on one line, rounded to six digits after the decimal point. Pad with zeros so that six digits always appear.

Examples2

Example 1
Input
```
6
1 1
5 3
3 3
3 1
1 3
5 1
```
Expected output
```
5.656854
```
Example 2
Input
```
3
7 -5
7 0
7 9999
```
Expected output
```
0.000000
```