2019_有向直线2中值问题

给定一条有向直线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上增设两处服务机构的最小服务转移费用。

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

输出最小服务转移费用

9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1

26