题目描述

明明家从1号站点出发，开车去旅游，一共要经过n个站点，依次为2、3……n。

由于明明带上了心爱的小猫，在每个站点都要为小猫提供一条鱼用做美餐（包括1号站点）。

除了1号站点只能吃1号站点买的鱼，其他站点既可以吃当地买的鱼，也可吃之前经过的站点买了存入车载冰箱中的鱼。

但车载冰箱消耗的电能来自汽油，所以每条鱼用冰箱保存到下一站的费用与各个站点的汽油价格有关。为使问题简化，我们约定：

----车从某站开出时油箱中都是此站点刚加的汽油。

----车载冰箱能容纳一路上需要的所有鱼。

即：每条鱼的费用既包括购买时的费用，也包括用冰箱保存鱼的费用。

为了降低小猫吃鱼的总代价，明明预先上网查到了这n个站点的鱼价和汽油价格。并据此算出每个站点买一条鱼的费用以及从该站点到下一站用冰箱保存一条鱼的费用。你能帮明明算出这一路上小猫吃鱼的最小总费用吗？

输入格式

第一行一个正整数n(1≤n≤100)，代表站点数；

接下来的n行：每行两个以空格分隔的正整数，表示：这一站买一条鱼的费用，以及从这一站把每条鱼保存到下一站的费用，两个费用均为小于10000的正整数。

最小总费用，是一个正整数。

一共5站，

第1个站点（起点）买鱼6元，运费3元，第一站必须先购买一条，总花费6元；

第2个站点买鱼7元，运费1元，从上一站最小花费+运费9元,大于本站购买的费用7，所以选择从本站购买鱼，总花费6+7=13元；

第3个站点买鱼3元，运费2元，从上一站最小花费+运费8元，大于本站购买的费用3，所以选择从本站购买鱼，总花费6+7+3=16元；

第4个站点买鱼8元，运费3元，从上一站最小花费+运费5元，小于本站购买的费用8，所以选择从上一站花费加上本站运费，总花费6+7+3+5=21元；

第5个站点买鱼9元，运费5元，从上一站最小花费+运费8元，小于本站购买的费用9，所以选择从上一站花费加上本站运费，总花费6+7+3+5+8=29元；

最终总花费为29元。

时间1000ms，内存256MiB