2490: 第10届蓝桥杯-猫吃鱼

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:14 Solved:13

Description

明明家从 1 号站点出发,开车去旅游,⼀共要经过 n 个站点,依次为 1,2、3......n。 由于明明带上了⼼爱的小猫,在每个站点都要为⼩猫提供一条⻥用做美餐 (包括 1 号站点)。
除了 1 号站点只能吃 1 号站点买的⻥,其他站点既可以吃当地买的鱼,也可吃之前经过的站点买了了存入车载冰箱中的鱼。 但⻋载冰箱消耗的电能来⾃汽油,所以每条鱼用冰箱保存到下⼀站的费用与各个站点的汽油价格有关。
为使问题简化,我们约定: (1)车从某站开出时油箱中都是此站点刚加的汽油。
(2)⻋载冰箱能容纳⼀路上需要的所有鱼。 即:每条⻥的费⽤既包括购买时的费用,也包括⽤冰箱保存鱼的费用。 
编程实现:
为了降低小猫吃鱼的总代价,明明预先上网查到了这 n 个站点的鱼价和 汽油价格。并据此算出每个站点买一条鱼的费⽤以及从该站点到下一站用冰箱保存一条鱼的费用。你能帮明明算出这一路上⼩猫吃鱼的最⼩总费用吗?

Input

第⼀行:站点数 n,1<n<100。
接下来的 n 行:每⾏两个以空格分隔的正整数,表示:这⼀站买一条鱼的费用,以及从这⼀站把每条鱼保存到下一站的费用,两个费用均为小于 10000 的正整数。

Output

最⼩总费用,是一个正整数。

Sample Input Copy

5
6 3
7 1
3 2
8 3
9 5

Sample Output Copy

29