“火之国”以其“火之神庙”——阿提什佳赫（Ateshgah）而闻名。为了容纳更多游客，作为一名首席建筑师，你计划建造更多的神庙。你有一名建筑工和 $n$ 座需要建造的神庙。神庙从 $0$ 到 $n - 1$ 进行编号。根据规划，每座神庙 $i$ 都有一个前置神庙 $p[i]$，必须在建造神庙 $i$ 之前建好。只有神庙 $0$ 满足 $p[0] = -1$，这意味着这座神庙可以在时刻 $0$ 立即开始建造。神庙 $i$ 需要花费 $d[i]$ 秒来建造，如果在时刻 $t$ 完工，其花费为 $t \times u[i]$。

求建造所有神庙的最小总花费。

实现细节

你需要实现以下函数：

int64 scheduling_cost(int[] p, int[] u, int[] d)

• p、u 和 d：长度为 $n$ 的整数数组。
• 该函数应返回建造所有神庙的最小花费。

样例

样例输入 1

scheduling_cost([-1, 0, 0], [5, 2, 5], [3, 4, 1])

样例输出 1

51

数据范围

• $1 \le n \le 200\,000$
• $p[0] = -1$
• 对于所有 $1 \le i \le n - 1$，有 $0 \le p[i] \le i - 1$
• 对于所有 $0 \le i \le n - 1$，有 $0 \le u[i] \le 10\,000$
• 对于所有 $0 \le i \le n - 1$，有 $0 \le d[i] \le 10\,000$

子任务

1. （5 分）对于所有 $1 \le i \le n - 1$，$p[i] = i - 1$
2. （7 分）对于所有 $1 \le i \le n - 1$，$p[i] = 0$ 且对于所有 $0 \le i \le n - 1$，$d[i] = 1$
3. （12 分）对于所有 $1 \le i \le n - 1$，$p[i] = 0$
4. （18 分）神庙 $0$ 最多是另外 $2$ 座神庙的前置神庙，且所有其他神庙最多是另外 $1$ 座神庙的前置神庙。
5. （21 分）$n \le 200$
6. （37 分）无附加限制。

样例评测程序

样例评测程序按以下格式读取输入：

• 第 1 行：$n$
• 第 2 行：$p[0]\ p[1]\ p[2]\ \dots\ p[n-1]$
• 第 3 行：$u[0]\ u[1]\ u[2]\ \dots\ u[n-1]$
• 第 4 行：$d[0]\ d[1]\ d[2]\ \dots\ d[n-1]$

样例评测程序输出单行，包含 scheduling_cost 的返回值。