邮递机器人

邮递机器人

测试数据来自 system/1573

背景

2009NOIP余姚中学内部暑期集训
7月12号模拟赛第三题

描述

这回不再是玩游戏的机器人了,而是专门分发包裹的邮递机器人。机器人从邮包中心出发,将邮包送往各个目的地。但是这个投递机器人有一个载重的上限,这就意味着它可能需要分很多次,才可以把所有的邮包投递出去。给定这个机器人的最大载重量。现在机器人随时可以出发,投递已经收到的邮包,但是有一个条件,投递的顺序必须按照邮包给出的先后顺序。

机器人一趟投递,从邮包中心(0,0)点,到达第一个邮包寄达的位置,然后依次到达最后一个邮包投递的位置,并返回邮包中心。任意两点之间的距离,是它们水平,垂直距离差距的和。机器人没单位距离走一步。例如,4个邮件,按顺序需要投递到(1,2),(1,0), (3,1), and (3,1)4个点。分2趟投递,每趟2个邮包。这样需要3+2+1=6,4+0+4=8。相同坐标的点之间的距离是0。

给出投递包裹的顺序,计算机器人最少需要移动的步数。

格式

输入格式

开始一个整数C,c<=1,000,000。表示机器人载重上限
一个整数N,N<=100,000。表示邮包个数。

N行,依次给出每个邮包的坐标,x,y以及该邮包的重量0<w<=c。

输出格式

输出机器人投递完所有邮包所需的最少步数。

样例1

样例输入1

10
4
1 2 3
1 0 3
3 1 4
3 1 4

样例输出1

14

限制

各个测试点1s

提示

30%的数据c<=100,n<=10000
100%的数据c<=1000000,n<=100000

信息

ID
1655
难度
(无)
分类
其他 | 排序 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者