背景

译自 NWERC 2018 A 题。

题目描述

某个知名程序设计竞赛正在考虑一种新的队伍摆放方式。比赛中共有 $n$ 支队伍，每支队伍都要被安排在一个无限大的体育馆中的某个位置 $(x,y)$。为了方便观察队伍，比赛方决定采用如下策略：

所有队伍都被分配了一个唯一的整数编号，范围为 $[1,n]$。对于任意两支编号分别为 $i$ 和 $j$ 的队伍，若 $i<j$，它们被放置在 $(x_i,y_i)$ 和 $(x_j,y_j)$，则必须满足 $x_i\le x_j$ 且 $y_i\le y_j$。

不幸的是，每支队伍的固定网络接入点已经被别人提前放好了。接入点体积较大，而且每个接入点只有一个端口，因此不同队伍的接入点位于不同位置。每支队伍都必须用一根直连 UTP 网线连接到自己的指定接入点。一根长度为 $\ell$ 的 UTP 网线的费用为 $\ell^2$。

请你为所有队伍选择摆放位置，使得队伍在两个坐标轴上的相对顺序都被保持，并且所需 UTP 网线的总费用最小。由于评委并不太担心隐私问题，允许两支或更多队伍被放在完全相同的位置，或者彼此任意接近。下图给出了一个例子。

:::align{center}

:::

输入格式

输入包括：

• 一行一个整数 $n$（$1\le n\le 10^5$），表示队伍数量。
• 接下来 $n$ 行，第 $i$ 行包含两个整数 $s_i,t_i$（$1\le s_i,t_i\le 10^6$），表示队伍 $i$ 的网络接入点位置。

任意两个接入点的位置不同。

输出格式

输出在一个最优合法布局中，将所有队伍连接到各自接入点所需的 UTP 网线总费用的最小值。

你的答案允许绝对误差或相对误差不超过 $10^{-6}$。

6
4 1
2 4
3 2
8 3
5 6
2 5

22.5

6
11 6
23 7
24 11
24 32
27 38
42 42

0

提示

【数据规模与约定】

具体限制见输入格式。