题解

题面描述

在某异界大陆，从城池$A$到达城池$B$需要经过若干个传送阵。$A$城设有起点传送阵，$B$城设有终点传送阵。所有传送阵按一条直线排列，相邻传送阵之间的距离均为$1$。每个传送阵具有以下两个属性：

1. 最大传送距离$L$：每次使用该传送阵可以选择向前传送至最多$L$个传送阵之外的位置。
2. 能量消耗$i$：每次使用该传送阵进行传送需要消耗$i$个能量水晶。

传送阵只能向前传送，无法向后传送。修士小明从$A$城出发，携带一定数量的能量水晶，目标是到达$B$城。请问小明最少需要携带多少个能量水晶，才能顺利到达$B$城。

题目内容

某异界大陆，从城池$A$到达城池$B$需要经历若干个传送阵，$A$城有起点传送阵，$B$城为终点，传送阵呈一字排开，相邻传送阵之间距离都为$1$。每个传送阵可传送距离是$1$到$L$，每次传送消耗的能量水晶$i$个，传送阵只能向前传送，不可向后。

修士小明携带若干能量水晶从$A$城出发，请问小明最少需要携带多少水晶才能到达$B$城。

输入描述

输入为多行:

第一行为整数$m(0<m<=10^4)$，表示接下来$m$行数组元素($m$个传送阵)

第二行至第$m+1$行为长度为2的整数数组，两个整数以空格隔开，第一个元素表示传送阵可传送的最大距离$L(0<L<=m)$，第二个元素表示该传送阵每次传送消耗的能量水晶个数$i(0<i<=10^4)$

输出描述

输出为整数，表示最少需要携带的水晶个数

样例1

输入

4
2 1
1 2
2 4
1 1

输出

5

说明

从下标$0$的传送阵出发，最优路径:

$0->2->B$城，,需要$5$个水晶。

到达B城最少需要$5$个水晶。

样例2

输入

4
1 1
2 2 
2 4
1 1

输出

4

说明

从下标$0$的传送阵出发，只能到达传送阵$1$，最优路径:

$0->1->3->B$城，,需要$4$个水晶。

到达B城最少需要$4$个水晶。