题目描述

有 $N$ 个地点沿单向环形道路依次排列。第 $i$ 个地点需要重量为 $w_i$ 的货物，从第 $i$ 个地点到下一个地点的距离为 $d_i$。可以选择一个地点修建农场，该地点的货物不需要运输。

货车从农场出发，开始时装有其他所有地点需要的货物，沿环形道路依次送货。经过一段道路的费用为当时车上货物总重量乘以该段距离。送完最后一处货物后返回农场的费用为 $0$。请计算最小总费用。

输入格式

第一行包含整数 $N$。 接下来 $N$ 行每行包含两个整数 $w_i,d_i$。

输出格式

输出一个整数，表示最小总费用。

样例

5
10 6
3 8
8 5
12 7
9 3

381

数据范围与提示

• $3 \le N \le 10^5$
• $1 \le w_i,d_i \le 100$