曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5988: 石油管的最优位置

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：25 Solved：15
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

Olay教授正在为一家石油公司咨询，公司正在计划建造一条由东向西的大型管道。该管道要穿过一个有n口井的油田。从每口井中都有一条喷油管沿最短路径与主管道直接相连(或南或北)，如图所示
 
给定各口井的x坐标和y坐标。问，Olay教授如何选择主管道的最优位置(即使得各喷管长度总和最小的位置)？

Input

第一行一个整数n
接下来n行，每行用空格隔开的两个整数x，y表示每口井的坐标

Output

一行一个答案，表示最小的各喷管长度总和

Sample Input Copy 

5
1 3
2 4
3 8
4 9
10 5

Sample Output Copy 

10

HINT

主管道建立在整数坐标上

1≤n≤100000

1≤x,y≤100000