P11678 [USACO25JAN] Watering the Plants P

Bessie 的花园中有 $N$ 株植物，从左到右编号为 $1$ 到 $N$（$2\leq N\leq 5\cdot 10^5$）。Bessie 知道植物 $i$ 至少需要 $w_i$（$0\leq w_i \leq 10^6$）单位的水。 Bessie 有一个十分古怪的灌溉系统，包含 $N-1$ 条水渠，编号为 $1$ 到 $N-1$。每条水渠 $i$ 有一个相关的单位费用 $c_i$（$1\le c_i\le 10^6$），Bessie 可以支付费用 $c_i k$ 来为植物 $i$ 和 $i+1$ 各提供 $k$ 单位的水，其中 $k$ 是一个非负整数。 Bessie 很忙，可能没有时间使用所有的水渠。对于每一个 $2\leq i \leq N$，计算仅使用前 $i-1$ 条水渠灌溉植物 $1$ 到 $i$ 所需要的最小费用。

输入的第一行包含一个正整数 $N$。 第二行包含 $N$ 个空格分隔的整数 $w_1, \ldots, w_N$。 第三行包含 $N-1$ 个空格分隔的整数 $c_1, \ldots, c_{N-1}$。

输出 $N-1$ 行，每行包含一个整数。第 $i-1$ 行包含使用前 $i-1$ 条水渠灌溉前 $i$ 株植物的最小费用。

样例 1 解释： 使用第一条水渠灌溉前 $2$ 株植物的最小费用是通过使用第一条水渠 $69$ 次，支付 $30 \cdot 69 = 2070$。 灌溉前 $3$ 株植物的最小费用是通过使用第一条水渠 $39$ 次，第二条水渠 $33$ 次，支付 $39 \cdot 30 + 29 \cdot 33 = 2127$。 - 测试点 $4$：$N \leq 200$，并且所有 $w_i \leq 200$。 - 测试点 $5\sim 6$：所有 $w_i \leq 200$。 - 测试点 $7\sim 10$：$N \leq 5000$。 - 测试点 $11\sim 14$：所有 $w_i$ 和 $c_i$ 独立地均匀随机生成。 - 测试点 $15\sim 19$：没有额外限制。