给定一条有向直线 L以及 L上的 n+1 个点x₀<x₁<……<x_n。 有向直线L上的每个点x_i都有一个权 w(x_i)；每条有向边 (x_i,x_i-1) 也都有一个非负边长d  (x_i,x_i-1) 。有向直线 L 上的每个点x_i 可以看作客户， 其服务需求量为w(x_i)。 每条边 (x_i,x_i-1) 的边长d  (x_i,x_i-1) 可以看作运输费用。如果在点x_i 处未设置服务机构，则将点x_i 处的服务需求沿有向边转移到点x_j处服务机构需付出的服务转移费用为 w(x_i)* d  (x_i,x_j) 。 在点x ₀处已设置了服务机构， 现在要在直线 L 上增设 2 处服务机构，使得整体服务转移费用最小。

对于给定的有向直线 L，计算在直线 L 上增设 2 处服务机构的最小服务转移费用。

输入数据。 第 1 行有 1 个正整数 n， 表示有向直线 L 上除了点x₀ 外还有 n 个点x₀<x₁<……<x_n。接下来的 n 行中，每行有 2 个整数。第 i+1 行的 2 个整数分别表示w(x_n-i-1)和d  (x_n-i-1,x_n-i-2) 。

将计算的最小服务转移费用输出。