3901 - 开心农场
A 市有一个有名的大湖，沿着大湖有N 个酒店，酒店形成了环状。酒店之间有一条单向的快速路，方便每天为各个酒店运送新鲜的蔬菜。
每个酒店能容纳的客人有限，因此每个酒店每天要消耗的蔬菜总量也基本上是能确定的，经过科学的统计，计算出了第 i 个酒店每天要消耗的蔬菜总量为 w_i 。
A 市决定在这 N 个酒店中选择其中的一个酒店，在它的旁边开设一个开心农场，专门为酒店提供蔬菜，酒店的选址成为当前最棘手的一个问题。
酒店选址很重要的一个标准，就是要使得运输的经费要尽可能的少，为了解决这一难题，A 市统计了从每个酒店经过单向快速路，到下一个酒店之间的距离。
每天，开心农场的超级大货车，会装满这些酒店所需要的所有蔬菜，从农场出发，沿着公路依次向各个酒店派送蔬菜。由于农场修建在其中一个酒店旁边，这个酒店就不需要运输了，直接安排人去农场将蔬菜搬回来就行。
运费的计算方式为，大货车运输的蔬菜的总重量 \times 距离的和。比如：下图中给出了 5 家酒店每家需要的蔬菜总量w_i，以及酒店之间的距离d_i，当货车运送完最后一家酒店蔬菜的回农场的这段路，由于货车是空的，可以视作运费为0。如果农场设在 1 号酒店旁，那么运费计算方式为：
从 1 号酒店装好总重量 = 3+8+12+9 = 32的蔬菜，也就是酒店 2 到 酒店 5 所需要的蔬菜，行驶距离为 6，需要运费为 32 \times 6。
到了 2 号酒店放下重量为 3 的蔬菜，带上重量为 29 的蔬菜，行驶距离 8 到 3 号酒店，需要运费 29 \times 8。
到了 3 号酒店放下重量为 8 的蔬菜，带上重量为 21 的蔬菜，行驶距离 5 到 4 号酒店，需要运费 21 \times 5。
到了 4 号酒店放下重量为 12 的蔬菜，带上重量为 9 的蔬菜，行驶距离 7 到 5 号酒店，需要运费 9 \times 7。
到了 5 号酒店放下重量为 9 的蔬菜，空车返回农场，也就是1号酒店的位置。
分析可知，将开心农场建在不同的酒店旁，最终的总运费是有差异的，请求出最小总运费是多少？
第 1 行输入一个整数 N，代表酒店的总数（3≤N≤10^5）。
接下来 N 行，每行有 2 个整数， w_i 和 d_i，分别代表了第i个酒店蔬菜消耗量 和 第i个酒店沿环形道路到下一个酒店的距离。（1≤w_i≤100，1≤d_i≤100）
对于 60\% 的数据 N ≤ 10^4。
对于 100\% 的数据 N ≤ 10^5。
输出最小的运输费用。
输入
5 10 6 3 8 8 5 12 7 9 3
输出
381
输入
10 1 2 4 9 10 40 100 100 5 9 70 80 100 80 80 90 100 95 90 80
输出
129973