旅行家问题2

题号：NC221820
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

显然，身为旅行家，爬山是他不能回避的问题。地图上存在 $N$ 座高度 $h_i$ ，由于这些山实在是太高惹，他们的宽度和彼此之间的距离都可以忽略不计。每座山的山顶存在一个高为 $x_i$ 的梯子，

他可以通过这个梯子到达高度可及的山顶，通俗的来说从高山i的山顶，可以转移到 $h_j \leq h_i+x_i$ 的高山j的山顶上去，同时交付 $x_i$ 的梯子使用费。

如果他想达到当前山顶的梯子高度所不能及的高山，他便需要搭乘飞机并交纳 $h_j-h_i$ 的运输费。

旅行家从一号山出发，他需要访问所有高山并返回一号山，请你帮他设计一个路线，使他花费的费用最小。

第一行包含一个整数 
接下来  行，第  行包括两个正整数  ，表示第  个山的高度，山顶梯子的长度。

输出一个正整数，表示最小的花费。

示例1

复制

复制

最优的攀爬顺序：
从1到3号高山，使用梯子，总费用为9；
从3号到2号，使用梯子，总费用为10；
从2号到1号，使用梯子，总费用为11；

示例2

复制

复制