题目描述

在花老师的指导下，每周四都有一个集会活动，俗称“浇水”活动。（具体浇水活动详情请见BZOJ3153，但这不是重点）

花神出了好多题，每道题都有两个参考系数：代码难度和算法难度。

花神为了准备浇花集会的题，必须找一道尽量适合所有人的题。

现在花神知道每个人的代码能力 $x$ 和算法能力 $y$，一道题（代码难度 $X$ 算法难度 $Y$）对这个人的不适合度为 $\max(|X–x|,|Y–y|)$。

也就是说无论太难还是太简单都会导致题目不适合做。（如果全按花神本人能力设题，绝对的全场爆0的节奏，太简单，则体现不出花神的实力）

当然不是每次都如花神所愿，不一定有一道题适合所有人，所以要使所有人的不合适度总和尽可能低。

花神出了 $100001^2$ 道题，每道题的代码难度和算法难度都为 ${0,1,2,3,……,100000}$。

输入格式

第一行一个正整数 $n$，表示花神有 $n$ 个学生，花神要为这 $n$ 个学生选一道题。

接下来 $n$ 行，每行两个空格隔开的整数 $x_i,y_i$，表示这个学生的代码能力和算法能力。

输出格式

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

3
1 2
2 1
3 3

3

数据规模与约定

• 对于 $100\%$ 的数据，$n \leq 10^5$，$0 \leq x_i,y_i \leq 10^5$。

题目来源

mjmjmj 命题

Stilwell 制作数据