该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

退役后的 cat 开始做游戏了，今天他发布了自己的第一款游戏《明文》。在这款游戏中，每个玩家发展自己的村庄，享受和平的村庄生活。

《明文》包含了一个在一维平面上的电力系统。最开始，有若干个发电站和建筑物。游戏目标是让电力系统中的每个发电站和建筑物连接在一起，最终形成一个连通的图形。玩家可以在游戏中建造一些中转站和电线来连接发电站和建筑物。

发电站和建筑物可以在没有电线的情况下连接到中转站，但是中转站必须通过电线相互连接。但是，发电站和建筑物不能直接相互连接，他们必须通过一个中转站连接。

接下来我们定义连接：

• 假设建筑物的坐标为 $x_i$，接受半径为 $r_i$，那么所有与建筑物距离不大于 $r_i$ 的中转站无需电线即可直接连接到它。也就是说，对于位于 $x$ 的中转站，其可以直接连接到位于 $x_i$ 的建筑物当且仅当 $|x - x_i| \leq r_i$。
• 与上文类似，假设发电站的供电半径为 $r_s$，那么所有和发电站距离不超过 $r_s$ 的中转站无需电线即可相互连接。
• 假设两个中转站的坐标为 $x_a,x_b$，那么玩家可以用电线连接他们，所需的电线长度为 $|x_a - x_b|$。并且每个中转站可以连接到任意数量（可以为 0）的发电站，建筑物和中转站。

为了让游戏对新手更友好，cat 决定开发 “配电GPT” 功能。在使用任意数量的中转站的情况下，玩家可以只选择一个发电站和几座建筑物来获得最佳的供电方案，该方案使用最短的总长度的电线来完成电力系统。但是，cat 不确定她的方案是否正确，因此你需要帮助他来计算最佳方案中使用的电线总长度，以确定她的方案的正确性。

请注意，即使坐标 $x$ 上存在发电站或建筑物，玩家仍然可以在坐标 $x$ 处建造一座新的中转站。同一坐标上可能有多个发电站或建筑物。

Input

第一行包含一个整数 $n$，代表发电站和建筑物总数。

第二行两个整数 $x_s,r_s$ 代表发电站的坐标和供电半径。

接下来 $n - 1$ 行，每行两个整数 $x_i,r_i$ 表示建筑物的坐标和接受半径。

Output

一行一个整数，表示最佳方案下使用最短电线的总长度。

Samples

5
0 1
0 3
5 1
6 1
9 2

1

样例1解释：

一个可能的方案是在 $1,3,4,6,7$ 处搭建中转站，用长度为 $1$ 的电线将位于 $3,4$ 的中转站连接起来。

2
-1000000000 1000000000
1000000000 1000000000

0

Limitation

本题采用 Subtask 形式评测。

Subtask #1（20分）$n \leq 100$

Subtask #2（20分）$n \leq 1000$

Subtask #3（30分）$n\leq 10^5$

Subtask #4（30分）$n \leq 2\times 10^5$

对于所有数据，有 $-10^9\leq x_i,x_s \leq 10^9,1 \leq r_i,r_s \leq 10^9$