题目描述

A市有一个有名的大湖，沿着大湖有$N$个酒店，酒店形成了环状。酒店之间有一条单向的快速路，方便每天为各个酒店运送新鲜的蔬菜。

每个酒店能容纳的客人有限，因此每个酒店每天要消耗的蔬菜总量也基本确定，第$i$个酒店每天消耗的蔬菜总量为$w_i$。

A市决定在这$N$个酒店中选择一个，在其旁边开设一个开心农场，专门为酒店提供蔬菜。农场选址的重要标准是使运输经费尽可能少，A市已统计出从每个酒店经过单向快速路到下一个酒店的距离。

每天，开心农场的超级大货车会装满所有酒店所需的蔬菜，从农场出发，沿公路依次向各个酒店派送。由于农场修建在某一酒店旁，该酒店无需运输，可直接派人到农场搬运蔬菜。

运费计算方式为：大货车运输的蔬菜总重量$\times$距离的和。需注意，货车运送完最后一家酒店蔬菜后返回农场的路程，因货车为空，运费视作$0$。

例如：当农场设在1号酒店旁时，货车从1号酒店装好酒店2到5所需的总重量蔬菜（即$3+8+12+9=32$），行驶距离6，运费为$32 \times 6$；到2号酒店放下3单位蔬菜后，带29单位蔬菜行驶距离8到3号酒店，运费$29 \times 8$；后续以此类推，直到5号酒店放下最后9单位蔬菜后空车返回。

不同农场选址对应的总运费不同，请求出最小总运费。

输入格式

1. 第1行输入一个整数$N$，代表酒店的总数（$3 \leq N \leq 10^5$）。
2. 接下来$N$行，每行有2个整数$w_i$和$d_i$，分别代表第$i$个酒店的蔬菜消耗量和第$i$个酒店沿环形道路到下一个酒店的距离（$1 \leq w_i \leq 100$，$1 \leq d_i \leq 100$）。

数据范围

• 对于60%的数据，$N \leq 10^4$。
• 对于100%的数据，$N \leq 10^5$。

输出格式

输出最小的运输费用。

样例输入1

5
10 6
3 8
8 5
12 7
9 3

样例输出1

381

样例1解释

从站点5出发，总费用为：99（5→1） + 138（1→2） + 160（2→3） + 60（3→4） = 381

样例输入2

10
1 2
4 9
10 40
100 100
5 9
70 80
100 80
80 90 
100 95
90 80

样例输出2

129973