SP17877 SAWMILL - Two Swamills

在一条从山顶延伸到山脚的道路旁种有 $n$ 棵老树。当地政府计划将这些树木砍伐，并且为了充分利用木材，需要将它们运送到锯木厂。 树木的运输只能沿道路向下进行。道路的最底端已设有一个锯木厂，你还可以在路的途中再建两个锯木厂。你的任务是选择两个锯木厂的位置，使得总运输成本最小化。运输费用按每米每千克木材一美分计算。

第一行输入一个整数 $n$，表示树的数量（$1 \le n \le 10^5$）。树木从山顶到底部依次编号为 $1, 2, \ldots, n$。接下来的 $n$ 行中，每行包含两个正整数，分别表示第 $i$ 棵树的重量 $w_i$（千克）以及第 $i$ 棵树与第 $i-1$ 棵树之间的距离 $d_i$（米）。注意，$d_n$ 表示第 $n$ 棵树到山脚的距离。保证将所有树木运送到山脚的锯木厂，所需的总费用小于 $10^{18}$ 美分。

输出一个整数，为运输的最小成本。

- $1 \le n \le 10^5$ - $1 \le w_i \le 10^9$ - $1 \le d_i \le 10^9$ - 总运输成本 $\sum_{i=1}^{n} w_i \cdot d_i < 10^{18}$ **本翻译由 AI 自动生成**