测试数据来自 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