题目描述

有 $n$ 座城市沿环岛公路依次编号为 $1$ 至 $n$，城市 $n$ 的下一座是城市 $1$。城市 $i$ 每天需要 $z_i$ 桶啤酒，到下一座城市的公路长 $d_i$。每桶啤酒每行驶一英里运费为一元，运输可以选择两个方向中较短的路线。选择一座城市建立酒厂，求供应所有城市的最少每日运费。

输入格式

第一行城市数 $n$。接下来 $n$ 行，每行两个整数 $z_i,d_i$。

输出格式

输出最少每日运费。

样例

6
1 2
2 3
1 2
5 2
1 10
2 3

41

数据范围

$5\le n\le10000$，$0\le z_i\le1000$，$d_i\ge0$，$\sum d_i\le100000$。