[Coci2011]rijeka

时间限制:10s      空间限制:128MB

题目描述

划一条船沿着河流从城镇0到城镇M。M+1个城镇可以看做是分布在一条直线
上。且相邻城镇之间的间隔恰好为1英里。有n个人需要从城镇ui到城镇vi去,
当你经过城镇ui时第i个人就上船了。需要在之后的过程中经过城镇vi,这样第
i个人才可以下船了。需要合理安排船的线路使得你经过的路径尽量短。 
 
 


输入格式


输出格式


样例输入

8 15 
1 12 
3 1 
3 9 
4 2 
7 13 
12 11 
14 11 
14 13 

样例输出

27

提示


n <= 300,000, M <= 10^9


题目来源

没有写明来源

Menuappsclose