#6098. 花神的浇花集会

题目描述

有 $n$ 个学生，第 $i$ 个学生的代码能力为 $x_i$，算法能力为 $y_i$。
花神要选一道题，该题的代码难度为 $X$，算法难度为 $Y$，其中 $X,Y$ 都是 $[0, 100000]$ 内的整数。
一道题对第 $i$ 个学生的不适合度为： [ \max(|X - x_i|, |Y - y_i|) ] 花神希望所有学生的不适合度总和最小。

输入格式

第一行一个正整数 $n$。
接下来 $n$ 行，每行两个整数 $x_i, y_i$。

输出格式

一个整数，表示最小的不适合度总和。

样例

输入

3
1 2
2 1
3 3

输出

3

解释
选择 $(X,Y) = (2,2)$：

• 对 $(1,2)$：$\max(|2-1|,|2-2|) = 1$
• 对 $(2,1)$：$\max(|2-2|,|2-1|) = 1$
• 对 $(3,3)$：$\max(|2-3|,|2-3|) = 1$
  总和 $1+1+1=3$。可以验证这是最小可能的总和。

数据范围与提示

• $n \leq 10^5$
• $0 \leq x_i, y_i \leq 10^5$

注意 $X,Y$ 的取值范围为 $0$ 到 $10^5$，共有 $(10^5+1)^2$ 种可能的题目。