Signals 2

Time limit1.5sMemory limit256 MB

Summary

Choose a subset of points with distinct x coordinates, sort them by x, and maximize the total Euclidean distance between consecutive chosen points.

Level: Medium7 of 10
Topics: Dynamic programming, Geometry, Sorting, Divide and conquer
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.

You build a communication system out of some of the signals. Line the chosen signals up in increasing order of $x$ coordinate and connect each neighboring pair in turn, so the chosen signals must all have different $x$ coordinates. The length of the system is the sum of the Euclidean lengths of the connecting segments. A system built from a single signal has length $0$ .

A longer system carries the transmission further. Find the length of the longest communication system.

Input

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

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

Output

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

Examples1

Example 1
Input
```
6
1 1
5 3
3 3
3 1
1 3
5 1
```
Expected output
```
5.6568542
```