好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

原题来自：ZJOI 2007

L 公司在山上有一些工厂。由于这座山处于高原内陆地区（干燥少雨），L 公司一般把产品直接堆放在露天，以节省费用。突然有一天，L 公司的总裁 L 先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是 L 先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。

L 公司在山上有 $N$ 个工厂。如图所示，工厂 $1$ 在山顶，工厂 $N$ 在山脚。由于地形的不同，在不同工厂建立仓库的费用可能不同。工厂 $i$ 目前已有成品 $P_i$ 件，在该厂建立仓库的费用为 $C_i$。对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于 L 公司产品的对外销售处设置在山脚的工厂 $N$，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，假设一件产品运送 $1$ 个单位距离的费用是 $1$。假设建立的仓库容量都足够大，可以容下所有的产品。

已知：

1. 工厂 $i$ 距离工厂 $1$ 的距离 $X_i$（其中 $X_1=0$）；
2. 工厂 $i$ 目前已有成品数量 $P_i$；
3. 在工厂 $i$ 建立仓库的费用 $C_i$。

请你帮助 L 公司寻找一个仓库建设的方案，使得总的费用（建造费用+运输费用）最小。

---

输入格式

第一行包含一个整数 $N$，表示工厂的个数。

接下来 $N$ 行，每行包含三个整数 $X_i, P_i, C_i$，意义如题中所述。

---

输出格式

仅包含一个整数，为可以找到最优方案的费用。

---

样例

样例输入

3
0 5 10
5 3 100
9 6 10

样例输出

32

样例说明

工厂数据：

1. X=0, P=5, C=10
2. X=5, P=3, C=100
3. X=9, P=6, C=10

最优方案：在工厂 $1$ 和工厂 $3$ 建立仓库。

• 工厂 $1$ 建立费用：10；
• 工厂 $3$ 建立费用：10；
• 运输费用：工厂 $2$ 的产品运到工厂 $3$，距离 $9-5=4$，运输费用 $4 \times 3 = 12$；
• 总费用 $10+10+12=32$。

如果只在工厂 $3$ 建立仓库：

• 工厂 $1$ 产品运到工厂 $3$：距离 $9-0=9$，费用 $9\times 5=45$；
• 工厂 $2$ 产品运到工厂 $3$：费用 $4\times 3=12$；
• 建造费用 $10$；
• 总费用 $45+12+10=67$，不如方案优。

---

数据范围

对于全部数据：

• $N \le 10^6$
• 保证所有的 $X_i, P_i, C_i$ 均在 int 范围以内
• 保证中间计算结果不超过 long long 范围

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

---

提示
此题为 斜率优化 DP 问题。

状态设计： 设 $dp[i]$ 表示在工厂 $i$ 建立仓库，且前 $i$ 个工厂的所有产品都得到妥善处理的最小总费用。

转移方程： 考虑上一个仓库建在 $j$（$0 \le j < i$），则 $(j, i]$ 之间的工厂的产品都运到 $i$ 仓库。

费用包括：

1. 在 $i$ 建仓库的费用 $C_i$；
2. 从 $j+1$ 到 $i-1$ 这些工厂的产品运到 $i$ 的运输费用；
3. $dp[j]$（前 $j$ 个工厂的最小费用）。

运输费用计算： 设 $sumP[i]$ 表示 $P_i$ 的前缀和，$sumXP[i]$ 表示 $X_i \times P_i$ 的前缀和。 则从 $k$（$j < k < i$）运到 $i$ 的费用为 $P_k \times (X_i - X_k) = P_k X_i - P_k X_k$。 总运输费用为：

$$X_i \times (sumP[i-1] - sumP[j]) - (sumXP[i-1] - sumXP[j])$$

因此转移方程为：

$$dp[i] = C_i + X_i \times (sumP[i-1] - sumP[j]) - (sumXP[i-1] - sumXP[j]) + dp[j]$$

整理得：

$$dp[i] = C_i + X_i \times sumP[i-1] - sumXP[i-1] + \min_{0 \le j < i} \{ dp[j] - X_i \times sumP[j] + sumXP[j] \}$$

令 $A_j = sumP[j]$, $B_j = dp[j] + sumXP[j]$，则：

$$dp[i] = C_i + X_i \times sumP[i-1] - sumXP[i-1] + \min_{0 \le j < i} \{ B_j - X_i \times A_j \}$$

斜率优化： 对于 $j_1 < j_2$，决策 $j_2$ 优于 $j_1$ 的条件为：

$$\frac{B_{j_2} - B_{j_1}}{A_{j_2} - A_{j_1}} \le X_i$$

由于 $X_i$ 单调递增（工厂从山顶到山脚距离递增），$A_j$ 单调递增（$P_i \ge 0$），因此可以用单调队列维护下凸包，队首为最优决策。

步骤：

1. 计算前缀和 $sumP[i]$, $sumXP[i]$；
2. 初始化队列，将 $j=0$ 入队（$A_0=0, B_0=0$）；
3. 遍历 $i$ 从 $1$ 到 $N$：
   • 若队首两点斜率 $\le X_i$，则弹出队首；
   • 取队首 $j$ 计算 $dp[i]$；
   • 将 $(A_i, B_i)$ 加入队尾，维护凸包（弹出队尾上凸点）；
4. 输出 $dp[N]$（注意：必须在 $N$ 建仓库吗？不一定，但我们可以虚拟一个 $N+1$ 工厂，距离为 $X_N$，$P_{N+1}=0, C_{N+1}=0$，然后答案取 $dp[N+1]$，或者直接算 $dp[N]$ 时认为 $N$ 必须建仓库，但实际最优方案可能不在 $N$ 建，不过由于产品只能往山下运，最后一个有产品的工厂必须建仓库，但 $P_i$ 可能为 0，所以需要小心。常见做法是：设 $dp[i]$ 表示前 $i$ 个工厂处理完毕的最小费用，不一定在 $i$ 建仓库，但这样转移更复杂。标准做法是：在 $N$ 建虚拟仓库，费用 0，距离不变）。

通常解法：设 $dp[i]$ 表示在 $i$ 建仓库且前 $i$ 个工厂处理完毕的最小费用，最后答案即为 $dp[N]$（因为产品只能往山下运，最后一个有产品的工厂必须建仓库，但 $P_N$ 可能为 0，不过 $N$ 建仓库费用可能不为 0，但我们可以选择不在 $N$ 建，而将产品运到更远的虚拟仓库？实际上因为销售处在 $N$，所以最终产品必须到 $N$，所以要么在 $N$ 建，要么在之前建并运到 $N$，但这样运输费用会增加。更常见的处理：在输入数据最后添加一个虚拟工厂 $N+1$，$X_{N+1}=X_N, P_{N+1}=0, C_{N+1}=0$，然后计算 $dp[N+1]$ 作为答案）。

复杂度 $O(N)$。