背景

在花老师的指导下,每周4都有一个集会活动,俗称“浇水”活动。

具体浇水活动详情请见BZOJ3153

但这不是重点

描述

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

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

 

现在花神知道每个人的代码能力x和算法能力y,一道题(代码难度X算法难度Y)对这个人的不适合度为    Max ( abs ( X – x ) , abs ( Y – y ) )

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

 

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

 

花神出了100001*100001道题,每道题的代码难度和算法难度都为0,1,2,3,……,100000

输入格式

第一行一个正整数N,表示花神有N个学生,花神要为这N个学生选一道题

接下来N行,每行两个空格隔开的整数x[i],y[i],表示这个学生的代码能力和算法能力

输出格式

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

样例输入

3
1 2
2 1
3 3

样例输出

3

数据范围与约定

对于30%的数据,n<=1000,0<=x[i],y[i]<=1000

对于100%的数据,n<=100000,0<=x[i],y[i]<=100000

样例解释

选一道代码难度为2,算法难度为2的题,就可得出最小的不合适度总和