炎热的夏日里，约翰带贝茜去水上乐园滑水。
滑水是在一条笔直的人工河里进行的，沿河设有 个中转站，并开通了 条滑水路线。路线的起点和终点总在某个中转站上，起点和终点可能相同。有些中转站可能是许多条路线的起点或终点，而有些站则可能没有在任何路线里被用上。
贝茜希望能把所有的路线都滑一遍。所有中转站排成一条直线，每个中转站位于离河的源头 米处。沿着河边的人行道，贝茜可以从任意位置走到任意一个中转站。中转站与滑水路线的布局满足下述的性质：任意两个中转站之间都有滑水路线直接成间接相连．水上乐园的入口与出口都在 号中转站旁，也就是说，贝茜的滑水路线的起点和终点都是 号中转站 。
为了更好地享受滑水的快乐，贝茜希望自己花在走路上的时间越少越好。请你帮她计算一下，如果按她的计划，把所有的路线都不重复地滑一遍，那她至少要走多少路。
输入格式：
第 行：两个整数 和 。
第 到 行 ： 第 行包括一个整数 表示第 号中转站距河源头的距离。
第 到 行 ：第 行包括两个整数 与 ，分别表示了一条滑水路线的起点和终点。
