当前没有测试数据。

题目描述

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

每个酒店能容纳的客人有限，因此每个酒店每天要消耗的蔬菜总量也基本上是能确定的，经过科学的统计，计算出了第 $i$ 个酒店每天要消耗的蔬菜总量为 $w_i$。

A市决定在这 $N$ 个酒店中选择其中的一个酒店，在它的旁边开设一个开心农场，专门为酒店提供蔬菜，酒店的选址成为当前最棘手的一个问题。

酒店选址很重要的一个标准，就是要使得运输的经费要尽可能的少，为了解决这一难题，A市统计了从每个酒店经过单向快速路，到下一个酒店之间的距离。

每天，开心农场的超级大货车，会装满这些酒店所需要的所有蔬菜，从农场出发，沿着公路依次向各个酒店派送蔬菜。由于农场修建在其中一个酒店旁边，这个酒店就不需要运输了，直接安排人去农场将蔬菜搬回来就行。

运费的计算方式为，大货车运输的蔬菜的总重量 $\times$ 距离的和。当货车运送完最后一家酒店蔬菜的回农场的这段路，由于货车是空的，可以视作运费为 $0$。

分析可知，将开心农场建在不同的酒店旁，最终的总运费是有差异的，请求出最小总运费是多少？

输入格式

第 $1$ 行输入一个整数 $N$，代表酒店的总数（$3 \le N \le 10^5$）。

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

输出格式

输出最小的运输费用。

样例 #1

输入

5
10 6
3 8
8 5
12 7
9 3

输出

381

样例 #2

输入

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

输出

129973

数据范围

对于 $60\%$ 的数据 $N \le 10^4$。

对于 $100\%$ 的数据 $N \le 10^5$。